Skip to content

Commit d8448f0

Browse files
MEDIUM/src/medium/CombinationSumII.java
1 parent 4b30789 commit d8448f0

File tree

1 file changed

+39
-0
lines changed

1 file changed

+39
-0
lines changed
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package medium;
2+
import java.util.*;
3+
4+
import utils.CommonUtils;
5+
public class CombinationSumII {
6+
7+
8+
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
9+
List<List<Integer>> result = new ArrayList();
10+
Arrays.sort(candidates);
11+
helper(candidates, target, 0, new ArrayList(), result);
12+
return result;
13+
}
14+
15+
void helper(int[] candidates, int target, int start, List<Integer> curr, List<List<Integer>> result){
16+
if(target > 0){
17+
for(int i = start; i < candidates.length && target >= candidates[i]; i++){
18+
if(i > start && candidates[i] == candidates[i-1]) continue;//skip duplicates, this is one difference from Combination Sum I
19+
curr.add(candidates[i]);
20+
helper(candidates, target - candidates[i], i+1, curr, result);//i+1 is the other difference from Combination Sum I
21+
curr.remove(curr.size()-1);
22+
}
23+
} else if(target == 0){
24+
List<Integer> temp = new ArrayList(curr);
25+
result.add(temp);
26+
}
27+
}
28+
29+
30+
public static void main(String...args){
31+
CombinationSumII test = new CombinationSumII();
32+
int[] candidates = new int[]{10,1,2,7,6,1,5};
33+
int target = 8;
34+
List<List<Integer>> result = test.combinationSum2(candidates, target);
35+
CommonUtils.printIntegerList(result);
36+
}
37+
38+
39+
}

0 commit comments

Comments
 (0)