/ Data Structure and Algorithms  

Leetcode 39. Combination Sum

Question



Given an array and a target value, find all unique combination of numbers that add up to target. The same number in the array can be used multiple times.

Similar Questions

Solution

The solution to this question is a classical backtracking algorithm. I will have another post to talk about backtracking in a lot more details. For this particular question, what we need to do is:

  • Keep adding numbers to result set. Until:
    • The sum equals the target
    • Or the sum is greater than the target
  • Either way, we remove the last added number and continue adding next number

For example, if the input array is [2, 3, 6, 7] and target is 7, the alroghtim runs as follows:

  • Add 2. Result = [2], Sum = 2
  • Add 2. Result = [2, 2], Sum = 4
  • Add 2. Result = [2, 2, 2], Sum = 6
  • Add 2. Result = [2, 2, 2, 2], Sum = 8. As Sum is greater than target, remove the last added number 2, new result = [2, 2, 2]
  • Add 3. Result = [2, 2, 2, 3], Sum = 9. As Sum is greater than target, remove the last added number 3, new result = [2, 2, 2]
  • Add 6. Result = [2, 2, 2, 6], Sum = 12. As Sum is greater than target, remove the last added number 6, new result = [2, 2, 2]
  • Add 7. Result = [2, 2, 2, 7], Sum = 13. As Sum is greater than target, remove the last added number 7, new result = [2, 2, 2]
  • No more numbers left in the array, so further remove the last number in the result, get new result = [2, 2]
  • Add 3. Result = [2, 2, 3], Sum = 7. As Sum equals to target, we add this result to the final list. And remove the last added number 3, new result = [2, 2]
  • Add 6. Result = [2, 2, 6], Sum = 10. As Sum is greater than target, remove the last added number 6, new result = [2, 2]
  • Add 7. Result = [2, 2, 7], Sum = 11. As Sum is greater than target, remove the last added number 7, new result = [2, 2]
  • No more numbers left in the array, so further remove the last number in the result, get new result = [2]
  • Add 6. Result = [2, 6], Sum = 8. As Sum is greater than target, remove the last added number 6, new result = [2]
  • Add 7. Result = [2, 7], Sum = 9. As Sum is greater than target, remove the last added number 7, new result = [2]
  • No more numbers left in the array, so further remove the last number in the result, get new result = []
  • Add 3. Result = [3], Sum = 3
  • …..so on and so forth
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> results = new ArrayList<>();

    backtrack(results, new ArrayList<>(), candidates, target, 0);

    return results;
}

private static void backtrack(List<List<Integer>> results,
                                List<Integer> tempList,
                                int[] candidates,
                                int remaining, 
                                int start) {
    if (remaining < 0) {
        return;
    } else if (remaining == 0) {
        results.add(new ArrayList<>(tempList));
    } else {
        for (int i = start; i < candidates.length; i++) {
            tempList.add(candidates[i]);

            backtrack(results, tempList, candidates, remaining - candidates[i], i);

            // find solution or remaining < 0, backtrack one number in the list
            tempList.remove(tempList.size() - 1);
        }
    }
}