Reference: Problem I & Problem II & Problem III
Difficulty: Medium

My Post: [全家桶] Combination Sum I, II, III with Detailed Explanation & Complexity Analysis

Problem I

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.
    • Why positive? Explanation below.
  • The solution set must not contain duplicate combinations.

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

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

Backtracking

First, let’s go through all pre-conditions one by one.

Used More Than Once:

It means that, for example [1, 2, 3], target = 3, we can pick 1 for three times. Therefore, if we pick 1, the subproblem is still [1, 2, 3]; if we pick 2, the subproblem is still [2, 3]. Note: It is not [1, 2, 3] since picking previous elements would lead to duplicate results, e.g. [1, 2] and [2, 1]. Therefore, it satisfies unique combinations.

Since the size of the subproblem does not decrease, how do we know when to stop? Sorting. We would pick elements in an increasing order. If we find that the current element curr we’ve picked leads to a sum greater than target, we assure that the subsequent elements (greater than curr) would also leads to a sum greater than target.

No Negative Elements:

Since we can pick an element more than one time, we can’t allow negative elements. Consider [-2, 1, 2], target = 1. The result could be [1], [-2, 1, 2], [-2, -2, 1, 2, 2], ....

Without Duplicates:

We can pick an elements more than one time! Actually, we can convert Problem I to Problem II, and use the solution in Problem II. See details in Complexity Analysis section.

Note: See comments.

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
29
30
31
32
33
34
public List<List<Integer>> combinationSum(int[] candidates, int target) {
  if (candidates == null || candidates.length == 0) {
    return new ArrayList<>(); // or null
  }
  int n = candidates.length;
  Arrays.sort(candidates); // sorting (since we need pruning)
  List<List<Integer>> result = new ArrayList<>();
  backtracking(0, target, candidates, new ArrayList<>(), result);
  return result;
}

private void backtracking(int depth, int target, int[] candidates, List<Integer> sol, List<List<Integer>> result) {
  int n = candidates.length;
  
  // base cases
  if (target == 0) { // add
    result.add(new ArrayList<>(sol));
    return;
  }
  if (depth == n) { // no more elements
    return;
  }
  
  for (int i = depth; i < n; ++i) {
    int curr = candidates[i]; // use it
    int nextTarget = target - curr;
    if (nextTarget < 0) { // pruning
      break; // do not examine later elements since they are larger
    }
    sol.add(curr);
    backtracking(i, nextTarget, candidates, sol, result);
    sol.remove(sol.size() - 1); // restore
  }
}

Problem II

Differences:

  • Each number in candidates may only be used once in the combination.
  • Contains duplicates.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

Backtracking

See the example below to have an intuition of how to handle duplicate results.

1
2
3
4
5
6
7
8
9
// Example
[2, 5, 2, 1, 2], target = 6
[1, 2, 2, 2, 5]   after sorting
In the first call,
A: Pick 1, then the subproblem becomes [2, 2, 2, 5].
B: Pick 2, then the subproblem becomes [2, 2, 5].
C: Pick 2, then the subproblem becomes [2, 5].
Consider: Does B include results in C? YES!
B includes all combinations that C could have. Also, B considers combinations like [2, 2, 2] that should be in the result list.

Therefore, in a subproblem [a, b, c, d, ...], if we have picked a and go into the subproblem [b, c, d, ...], we should not pick b and go into the subproblem [c, d, ...] when a == b.

The good news is sorting makes this checking not so difficult. We just need to check the previous element in the for-loop. This is a common approach to handle duplicates.

Note: One final caveat is about the order of two base cases.

1
2
3
4
5
6
7
8
9
// correct!
if (target == 0) {
  result.add(new ArrayList<>(sol));
  return;
}

if (depth == n) {
  return;
}

What would have gone wrong if we put if (depth == n) in the first place?

Consider a test case like [1, 2, 5], target = 5. [5] won’t be added to the result list since depth == n is satisfied.

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
29
30
31
32
33
34
35
36
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  if (candidates == null || candidates.length == 0) {
    return new ArrayList<>();
  }
  Arrays.sort(candidates); // sorting
  List<List<Integer>> result = new ArrayList<>();
  backtracking(0, target, candidates, new ArrayList<>(), result);
  return result;
}

private void backtracking(int depth, int target, int[] candidates, List<Integer> sol, List<List<Integer>> result) {
  int n = candidates.length;
  // base cases
  if (target == 0) {
    result.add(new ArrayList<>(sol));
    return;
  }
  
  if (depth == n) {
    return;
  }
  
  for (int i = depth; i < n; ++i) {
    if (i > depth && candidates[i - 1] == candidates[i]) { // handle duplicates (not i > d)
      continue;
    }
    int curr = candidates[i];
    int nextTarget = target - curr;
    if (nextTarget < 0) {
      break;
    }
    sol.add(curr);
    backtracking(i + 1, nextTarget, candidates, sol, result); // i + 1 --> used once
    sol.remove(sol.size() - 1); // restore
  }
}

Complexity Analysis

Reference:

First, we need to understand how it works in Problem II. The time complexity is $O(k \times 2^N)$, where $k$ is the average length of each possible solution. Copying such a possible solution list takes $O(k)$ time.

Solution Space: Since each element is used only once (use it or not), intuitively we would say the size of the solution space is at most $2^N$. Also, it can be interpreted as the sum of C(n, k) (which is $2^N$) where k = 0...n is the size of the solution list. Notice that after sorting ($O(N\log{N})$), we can do pruning, which in fact we don’t need to explore that many solutions.

If we do not consider the result list, the space complexity is bounded by $O(N)$ because of at most $N$-size recursion stack and $N$-size of when copying list.

Problem I (Conversion to Problem II):

For example, [2, 3, 4, 5, 6], target = 10 in Problem I, could be converted to [2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6], target = 10 in Problem II. At this time, each element can be used only once. The question is how can we determine the new size of the array, i.e. N'?

For each element, the number of each element is determined by ceil(target/E) where E is the element. For example, E = 2, target = 10, we allow 5 2s in the new array.

By this conversion, we can then do the complexity analysis using the method in Problem II.

Problem III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

  • All numbers will be positive integers.
  • The solution set must not contain duplicate combinations.
  • ALso, I think each number is used once.

Example:

1
2
3
4
5
Input: k = 3, n = 7
Output: [[1,2,4]]

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

Backtracking

Based on the same idea, we can readily write the following code.

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>> combinationSum3(int k, int n) {
  if (k == 0 || n == 0) {
    return new ArrayList<>();
  }
  List<List<Integer>> result = new ArrayList<>();
  backtracking(1, k, n, new ArrayList<>(), result);
  return result;
}

private void backtracking(int num, int k, int n, List<Integer> sol, List<List<Integer>> result) {
  // reject & accept
  if (sol.size() == k) {
    if (n == 0) {
      result.add(new ArrayList<>(sol));
    }
    return;
  }
  
  for (int i = num; i <= 9; ++i) { // for number 1 ~ 9
    int nextTarget = n - i;
    if (nextTarget < 0) { // consider this line (can we put it into the base case?)
      break;
    }
    sol.add(i);
    backtracking(i + 1, k, nextTarget, sol, result);
    sol.remove(sol.size() - 1); // restore
  }
}

I think about how to make the code more readable and efficient.

Break The Loop Early:

Instead of returning in the base case, we add break logic in the for-loop. It prunes many subsequent computations.

1
2
3
if (nextTarget < 0) {
  break;
}

Base Case:

Although we know that n < 0 won’t occur because checking before backtracking (if (nextTarget < 0)), we don’t check if n < 0 in the base-case section.

I think it is still better to follow the logic: 1) finish condition, 2) accept condition. The second condition is inside the first condition.

1
2
3
4
5
6
7
8
9
// base case
if (sol.size() == k || n <= 0) { // finish condition
  // accept
  if (sol.size() == k && n == 0) {
    result.add(new ArrayList<>(sol));
  }
  // reject
  return;
}

Time: $O(K \times 9^K)$
Space: $O(K)$

Reference: Zhiyuan_Yao

Since we have a pool of 9 number to choose from, let’s say the pool size is P (in this case P = 9) and each node can have at most P branches (in actual cases, it is in most time less than P). This backtracking can at most have (K + 1) levels. So, time complexity is less than $O(K \times P^K)$ (copying K-size list takes $O(K)$).