Combination Sum

The problem

You are given a list of different positive numbers, candidates, and a number target. Return every combination of candidates that adds up to target.

You may use the same number as many times as you like. Two combinations are the same if they use the same numbers the same number of times, in any order, so list each one only once. The answer can be in any order.

Example 1

Input: candidates = [3, 4, 5], target = 10

Output: [[3, 3, 4], [5, 5]]

3 + 3 + 4 = 10 and 5 + 5 = 10. The picture shows every call the search makes: green marks the two that reach 0.

Example 2

Input: candidates = [6], target = 4

Output: []

The only number is already bigger than the target.

Example 3

Input: candidates = [1, 2], target = 3

Output: [[1, 1, 1], [1, 2]]

[2, 1] is the same combination as [1, 2], so it is not listed again.

Constraints

• 1 ≤ candidates.length ≤ 30 (call this n)
• 2 ≤ candidates[i] ≤ 40, all different (call the smallest M)
• 1 ≤ target ≤ 40 (call this T)
• The answer has fewer than 150 combinations.

Clarifying questions

Can a number be used more than once?

Yes, as often as we like. That is the main difference from similar problems.

Are [3, 4, 3] and [3, 3, 4] different answers?

No. Order does not matter, so each set of numbers appears once.

Can a candidate be 0 or negative?

No. Every number is at least 2, so each pick moves strictly closer to the target.

Can there be duplicates in candidates?

No. All numbers are different, which is why no extra step is needed to skip repeats.

Spot the pattern

The question asks for every combination, not just how many. That means listing them, and the way to list choices is backtracking: pick a number, solve the smaller problem with what is left, then undo the pick and try the next number. Because every number is positive, the amount left only shrinks, so each branch ends.

Solutions

BacktrackingO(n^(T/M))

Show all

There is only one approach worth showing. The answer itself can be large, so some search over the choices is needed, and this one never builds the same set twice.

Backtracking O(n^(T/M))

The idea

Sort the candidates. Then grow a combination one number at a time, and track how much is still left to reach.

• If nothing is left, the combination is an answer. Save a copy.
• Otherwise, try each candidate in turn. If it is bigger than what is left, stop: the list is sorted, so every later candidate is bigger too. If it fits, add it, solve the rest, and remove it again.

To avoid listing the same set twice in different orders, a call may only pick numbers from its own position onward. So every combination is built in non-decreasing order, like [3, 3, 4], and never as [4, 3, 3]. The next call starts at the same position, not the one after it, because a number may be used again.

Why it never misses the answer: every valid combination, written in sorted order, is one path down the tree of choices, and the search follows every path that does not overshoot the target.

Walkthrough

combination

empty

result

empty

1. candidates.sort()
2. def backtrack(start, remaining):
3. if remaining == 0:
4. result.append(combination.copy()); return
5. for i in range(start, len(candidates)):
6. if candidates[i] > remaining: break
7. combination.append(candidates[i])
8. backtrack(i, remaining - candidates[i])
9. combination.pop()
10. backtrack(0, target)

Sort the candidates: [3, 4, 5]. Each node below is one call; its number is the amount still to reach. Start with 10.

← BackStep →Play1 / 13

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private int[] candidates;
    private final List<List<Integer>> result = new ArrayList<>();
    private final List<Integer> combination = new ArrayList<>();

    // Backtracking: build each combination in non-decreasing order, so
    // every set is made once. Each branch stops as soon as it overshoots.
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // Sorted, a candidate that is too big means all later ones are too.
        this.candidates = candidates.clone();
        Arrays.sort(this.candidates);
        backtrack(0, target);
        return result;
    }

    private void backtrack(int start, int remaining) {
        if (remaining == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }
        // Only pick from start onward: going back would build the same
        // set again in another order, like [4, 3, 3] after [3, 3, 4].
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;
            combination.add(candidates[i]);
            // Pass i, not i + 1: the same number may be used again.
            backtrack(i, remaining - candidates[i]);
            // Undo the choice before trying the next number.
            combination.remove(combination.size() - 1);
        }
    }
}

Big O

Time O(n^(T/M))Space O(T/M)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion, so we count the calls of backtrack. Inside a call, each run of the loop either starts one more call or stops the loop. So the loop work is at most one step per child call plus one, and each call counts as 1 step plus its children.

   1. candidates.sort()
   2. def backtrack(start, remaining):
   3. if remaining == 0:
   4. result.append(combination.copy()); return
   5. for i in range(start, len(candidates)):
   6. if candidates[i] > remaining: break
   7. combination.append(candidates[i])
   8. backtrack(i, remaining - candidates[i])
   9. combination.pop()
   10. backtrack(0, target)

2. 2 Count the runs on Example 1

   The table counts calls by depth, which is the number of picks so far. The first call has 3 children. Below that, the branches thin out fast, because big picks leave little room.

   1 + 3 + 6 + 2 = 12 calls.

   depth	0	1	2	3
   calls	1	3	6	2

   total

   1 + 3 + 6 + 2 = 12 calls

3. 3 Write the count for any n

   Every pick is at least M, so a path can hold at most T / M picks before the amount left runs out. Each call has at most n children. So depth d holds at most nᵈ calls:

   1 + n + n² + … + n^(T/M) calls

   Check it with Example 1: n = 3 and T / M = 10 / 3, so at most 3 picks. The bound is 1 + 3 + 9 + 27 = 40. The real run made 12, because most branches overshot early.

4. 4 Keep only the part that grows fastest

   The last term is bigger than all the others together, at least when n is 2 or more. So the sum is less than 2 × n^(T/M). Drop the 2. Copying a finished answer costs up to T / M more steps, but that only happens for answers, and there are fewer than 150. What is left is n^(T/M): exponential, which is fine here because T is at most 40.

   So the time is O(n^(T/M)).

5. S Space: count the extra memory the same way

   combination holds at most T / M numbers, and the call stack is at most T / M + 1 calls deep. So the extra space is O(T/M), not counting the answer itself.

   combination (up to T / M numbers)call stack (T / M deep)

Common mistake

Starting every call from the first candidate

If each call loops over all candidates, the search builds [3, 3, 4], [3, 4, 3] and [4, 3, 3] as three answers. Passing start and looping from it keeps each combination in sorted order, so it appears once.

Tested at the limits

2,000 random inputs of 1 to 5 candidates from 2 to 12 and a target up to 20, so some have many combinations and some have none. The backtracking gave the same combinations every time as a simple check that tries every count of each candidate.

Largest inputs	Result
30 candidates and target 40 (the most allowed), picked so the answer has 149 combinations, just under the limit of 150. Backtracking.	Under 0.01 s, and about 0.015 MB of extra memory: one combination being built, plus the answer itself.
30 candidates with 2 as the smallest, target 40, 139 combinations. Long paths of 2s, up to 20 numbers deep. Backtracking.	Under 0.01 s, and about 0.015 MB of extra memory. A path is at most T / M = 20 numbers long.