LeetCode: Combination Sum

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]都会出现。

这里的排序与消除重复结果无关,这里仅是为了让结果中排列是有顺序的。

LeetCode: Combination Sum
 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     }
LeetCode: Combination Sum

LeetCode: Combination Sum

上一篇:poj3045Cow Acrobats(贪心, 二分)


下一篇:WPS目录制作方法