|
| 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