Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
找到全部解，一看就是一个dfs的节奏。dfs需要判断循环起始的位置。
需要注意的地方是，因为一个数字可以无限次的出现，所以每次dfs的起始位置不是上一次加1，而是与上一次相同，这样的话就可以重复选一个数字了。
起始位置也不能是0，因为这样会出现重复的情况。比如[1,1,3]与[3,1,1]都会出现。
这里的排序与消除重复结果无关，这里仅是为了让结果中排列是有顺序的。
1 public static ArrayList<ArrayList<Integer>> combinationSum(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, 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 }