[LeetCode] 39. Combination Sum

Posted on | In

Problem

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Explanation 1

  1. We can use recursion to solve this problem.

  2. First, we create a result list and a sub temporary sublist, passing these two lists as the parameters to the helper function. Also, we pass the start index initialize to 0 to the helper function. The start index is used to avoid duplicate sublist. For example, if condidates=[1, 2, 3], then if we already push the sublist [1, 2] into the result list, then we don’t want to put [2, 1] into the result list. In other words, after we finding out all the sublist that starts with 1, we then need to find out all the sublist that starts with 2.

  3. The base case if target == 0, we push the sublist into the result list, and return. If the target < 0, we just return.

  4. Note, when we push the temporary sublist into the result list, we will pass the new object of temporary sublist, not the reference of original temporary sublist since it will change everytime.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    void helper(int[] candidates, int target, List<List<Integer>> res, List<Integer> temp, int start) {
        if (target == 0) {
            res.add(new ArrayList<>(temp));
            return;
        } else if (target > 0) {
            for (int i = start; i < candidates.length; i++) {
                if (candidates[i] > target) break;
                temp.add(candidates[i]);
                helper(candidates, target-candidates[i], res, temp, i);
                temp.remove(temp.size()-1);
            }
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) return res;
        Arrays.sort(candidates);
        List<Integer> temp = new ArrayList<>();
        helper(candidates, target, res, temp, 0);
        return res;
    }
}

Explanation 2

  1. We can also solve this problem using dynamic programming. Let’s use the problem’s Example 1. We first create a dp array dp[] and dp[t] represents all the combinations for target t.

  2. Loop through all the candidates, for each candidate c, inner loop through target t from 1 to target inclusive. If c > t, we can skip. Else if c == t, we find one combination for target t, which is [c], so we append this combination to dp[t]. Else if c < t, assume c is part of the combination, then we need to find all the combinations for dp[t - c], and for each combination, we append c to it, now this combination become the combination for dp[t].

1
2
3
4
5
    0       1       2       3      4       5      6       7
2   -       -      [2]      -    [2, 2]    -   [2,2,2]    -
3   -       -       -      [3]     -       -     [3,3]  [2, 2, 3]  
6   -       -       -       -      -       -     [6]      -
7   -       -       -       -      -       -      -      [7]

Solution 2

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>>[] dp = new ArrayList[target + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new ArrayList<>();
        }

        for (int c: candidates) {
            for (int t = 1; t <= target; t++) {
                if (c > t) continue;
                else if (c == t) {
                    dp[t].add(new ArrayList(Arrays.asList(c)));
                } else {
                    for (List<Integer> lst: dp[t - c]) {
                        List<Integer> sub = new ArrayList<>(lst);
                        sub.add(c);
                        dp[t].add(sub);
                    }
                }
            }
        }

        return dp[target];
    }
}