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.
这里数字不需要重复出现，所以使用dfs的时候，循环从上一次的下一个位置开始就可以了。
但是这样会出现重复的结果。比如[1,2,3,1]，因为第一个位置可以选两次1，所以可能会出现重复结果。
所以这里排序是为了方便避免重复的结果。[1,1,2,3]，当为第一个位置选择时，就不必要选两次1了。
1 public static ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) { 2 Arrays.sort(candidates); 3 ArrayList<Integer> tmp = new ArrayList<Integer>(); 4 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 5 process(candidates, 0, tmp, result, 0, target); 6 return result; 7 } 8 9 public static void process(int[] candidates, int start, ArrayList<Integer> tmp, ArrayList<ArrayList<Integer>> result, 10 int sum, int target) { 11 if (sum == target) { 12 result.add(new ArrayList<Integer>(tmp)); 13 return; 14 } 15 else if (sum < target) { 16 for (int i=start; i<candidates.length; i++) { 17 tmp.add(candidates[i]); 18 process(candidates, i+1, tmp, result, sum+candidates[i], target); 19 tmp.remove(tmp.size()-1); 20 while(i<candidates.length-1 && candidates[i] == candidates[i+1]) i++; 21 } 22 } 23 }