# 39. Combination Sum I & II & III

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

## 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:

### 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 , [-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.

## Problem II

Differences:

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

Example:

### Backtracking

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

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.

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.  won’t be added to the result list since depth == n is satisfied.

## 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:

### Backtracking

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

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.

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.

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

Comment Junhao Wang
a software engineering cat