Combination Sum II

https://leetcode.com/problems/combination-sum-ii/

After completely understanding the previous post, this one becomes a piece of cake, all I did was to change to recursive call inside the function from  to i+1, this way, it will not add the same number when trying to find one potential combination. Also, I used a set to filter out duplicate combinations (the reason for duplicate combinations to occur is because there might be duplicate numbers in the given array, which resulted in the same combination). Also, sorting the array in the first place matters, because we will exit the for loop once we find target is greater than candidates[i], if it’s not sorted, we’ll miss checking the rest of the numbers.


public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
//sort the candidates
Arrays.sort(candidates);

getResult(result, new LinkedList<Integer>(), candidates, target, 0);
return result;
}

void getResult(List<List<Integer>> res, LinkedList<Integer> curr, int[] candidates, int target, int start){
if(target > 0){
for(int i = start; i < candidates.length && target >= candidates[i]; i++){
curr.add(candidates[i]);
getResult(res, curr, candidates, target - candidates[i], i);
curr.remove(curr.size()-1);
}
} else if(target == 0){
res.add(new ArrayList<Integer>(curr));
}
}

public static void main(String...strings){
CombinationSum_20160718 test = new CombinationSum_20160718();
int[] candidates = new int[]{2,3,6,7};
int target = 7;
test.combinationSum(candidates, target);
}

Advertisements

Combination Sum

https://leetcode.com/problems/combination-sum/

I’m really impressed by this solution: https://discuss.leetcode.com/topic/7698/java-solution-using-recursive

I need to understand/grasp recursion more deeply to learn to apply it to solve different problems. Like this one, I should be able to solve it as proficiently as solving those DFS tree problems.

Notes:

  • In the recursive call, there are two base cases:
    1. when the target equals zero, that means, the current path curr is a valid combination, thus we’ll add it into the result
    2. the other base case is implicit, when the target is smaller than zero, it just returns, thus it also went back to after the recursive call, to this line: curr.remove(curr.size()-1); and then adds the next candidate number into curr and continue the recursion
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
//sort the candidates
Arrays.sort(candidates);

getResult(result, new LinkedList<Integer>(), candidates, target, 0);
return result;
}

void getResult(List<List<Integer>> res, LinkedList<Integer> curr, int[] candidates, int target, int start){
if(target > 0){
for(int i = start; i < candidates.length && target >= candidates[i]; i++){
curr.add(candidates[i]);
getResult(res, curr, candidates, target - candidates[i], i);
curr.remove(curr.size()-1);
}
} else if(target == 0){
res.add(new ArrayList<Integer>(curr));
}
}