[LeetCode] Combination Sum2

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

解题思路：
      1. 与combination sum基本一致，区别为每次都要移动到下一个不相同的数。

 public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List> res = new ArrayList>();
        List solution = new ArrayList();
        
        combination2(candidates, 0, target, res, solution);
        
        return res;
    }
    
    public void combination2(int[] candidates, int startIndex, int target, List> res, List solution){
        if(target == 0){
            List tmp = new ArrayList(solution);
            res.add(tmp);
            return;
        }
        
        for(int i = startIndex; i < candidates.length; i++){
            if(candidates[i] <= target){
                solution.add(candidates[i]);
                combination2(candidates, i+1, target - candidates[i], res, solution);
                solution.remove(solution.size() - 1);
                
                while(i < candidates.length - 1 && candidates[i] == candidates[i+1]) i++; //move to next diff candidate
            }else break;
        }
    }