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 allunique combinationsin 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**.

- Why positive?
- The solution set must not contain duplicate combinations.

**Example:**

1 | Input: candidates = [2,3,5], target = 8, |

### 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 | public List<List<Integer>> combinationSum(int[] candidates, int target) { |

## Problem II

**Differences:**

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

**Example:**

1 | Input: candidates = [10,1,2,7,6,1,5], target = 8, |

### Backtracking

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

1 | // Example |

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 | // correct! |

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 | public List<List<Integer>> combinationSum2(int[] candidates, int target) { |

## Complexity Analysis

Reference:

- If asked to discuss the time complexity of your solution, what would you say?
- Deadbeef-ECE’s GitHub: Problem I, Problem II

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

s 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 | Input: k = 3, n = 7 |

### Backtracking

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

1 | public List<List<Integer>> combinationSum3(int k, int n) { |

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 | if (nextTarget < 0) { |

**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 | // base case |

**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)$).