Combination Sum II leetcode java
浏览数：35 /
时间：2015年06月08日
题目：
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 (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
10,1,2,7,6,1,5 and target 8, A solution set is:
[1, 7] [1, 2, 5] [2, 6]
[1, 1, 6]
题解：
这道题跟combination sum本质的差别就是当前已经遍历过的元素只能出现一次。
所以需要给每个candidate一个visited域，来标识是否已经visited了。
当回退的时候，记得要把visited一起也回退了。
代码如下：
1 public static ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
3 ArrayList<Integer> item = new ArrayList<Integer>();
4 if(candidates == null || candidates.length==0)
5 return res;
6
7 Arrays.sort(candidates);
8 boolean [] visited = new boolean[candidates.length];
9 helper(candidates,target, 0, item ,res, visited);
10 return res;
11 }
12
13 private static void helper(int[] candidates, int target, int start, ArrayList<Integer> item,
14 ArrayList<ArrayList<Integer>> res, boolean[] visited){
15 if(target<0)
16 return;
17 if(target==0){
18 res.add(new ArrayList<Integer>(item));
19 return;
20 }
21
22 for(int i=start;i<candidates.length;i++){
23 if(!visited[i]){
24 if(i>0 && candidates[i] == candidates[i-1] && visited[i-1]==false)//deal with dupicate
25 continue;
26 item.add(candidates[i]);
27 visited[i]=true;
28 int newtarget = target - candidates[i];
29 helper(candidates,newtarget,i,item,res,visited);
30 visited[i]=false;
31 item.remove(item.size()-1);
32 }
33 }
34 }
2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
3 ArrayList<Integer> item = new ArrayList<Integer>();
4 if(candidates == null || candidates.length==0)
5 return res;
6
7 Arrays.sort(candidates);
8 boolean [] visited = new boolean[candidates.length];
9 helper(candidates,target, 0, item ,res, visited);
10 return res;
11 }
12
13 private static void helper(int[] candidates, int target, int start, ArrayList<Integer> item,
14 ArrayList<ArrayList<Integer>> res, boolean[] visited){
15 if(target<0)
16 return;
17 if(target==0){
18 res.add(new ArrayList<Integer>(item));
19 return;
20 }
21
22 for(int i=start;i<candidates.length;i++){
23 if(!visited[i]){
24 if(i>0 && candidates[i] == candidates[i-1] && visited[i-1]==false)//deal with dupicate
25 continue;
26 item.add(candidates[i]);
27 visited[i]=true;
28 int newtarget = target - candidates[i];
29 helper(candidates,newtarget,i,item,res,visited);
30 visited[i]=false;
31 item.remove(item.size()-1);
32 }
33 }
34 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
