Combination Sum

The problem

You are given a list of different positive integers, candidates, and a number, target. Return every combination of candidates that adds up to exactly target. A candidate may be used any number of times. Two combinations are the same when they use each number equally often, so [2, 2, 3] and [3, 2, 2] are one combination and appear once. The combinations, and the numbers inside each one, may come in any order. If no combination adds up to target, return an empty list. A target of 0 has one answer, the empty combination, because adding no numbers gives 0.

What to write

function solve(candidates: number[], target: number): number[][]

Input
candidates = [2,3,6,7]
target = 7

Output
[[2,2,3],[7]]

Input
candidates = [2,3,5]
target = 8

Output
[[2,2,2,2],[2,3,3],[3,5]]

Constraints

Distinct positive candidates; at most 8 candidates; target 0–30.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every candidate is positive, so each number you add makes the total larger, never smaller. A total that has passed target can never come back down. The order inside a combination does not count, so [2, 2, 3] and [3, 2, 2] are one answer and must appear once.

2. Hint 2: Ask a smaller question

   With the candidates 2 and 3 and a target of 7, find every way to reach 7 by hand. Did you write down both [2, 2, 3] and [2, 3, 2]? What rule about the order in which you pick numbers would let each combination turn up only once?

3. Hint 3: Name the pattern

   The signal is "return every combination that reaches the target". Build a combination one number at a time: choose a candidate, explore everything that can follow it, then take it back and choose the next candidate. Trying a choice, undoing it and trying the next one is backtracking. Read the lesson on backtracking.

4. Hint 4: State the invariant

   The chosen numbers never go down: after a candidate you may choose it again or a later one, never an earlier one. So each combination can be built in one order only. What is left always equals target minus the chosen numbers, and it never drops below 0.

5. Hint 5: Sketch the pseudocode

   Sort the candidates. explore(start, left, chosen): if left is 0, record a copy of chosen and return. For each position i from start on: stop the loop if the candidate at i is larger than left. Otherwise add it to chosen, call explore(i, left minus the candidate, chosen) and remove it again. Begin with explore(0, target, empty list).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Backtrack through candidates starting at a nondecreasing index. Reuse the current index when taking a value and stop when the remaining sum reaches zero.

The slow way

Write down every list of candidates whose total does not pass the target, in every order, and keep the lists that hit the target exactly. The same combination then turns up once per order. For example 1 that gives [2, 2, 3], [2, 3, 2], [3, 2, 2] and [7], so you still have to sort the lists and remove the repeats.

The insight

Two facts keep the search small. Every candidate is positive, so once a candidate is larger than what is left, it can never fit, and after sorting neither can any candidate behind it. And if you only ever choose the same candidate again or a later one, each combination can be built in one order only, so no repeats appear.

Step by step

1. Sort a copy of the candidates and keep a list for the answers. Sorted order is what makes stopping early safe: when one candidate is too large, every candidate after it is larger still. Sorting a copy leaves the caller's list as it was.
2. Extend the numbers chosen so far, from a start position. A call needs three facts: the numbers chosen so far, how much is still missing from the target, and the first candidate it may use. Nothing else about the past matters.
3. Nothing is left to add: record a copy of the chosen numbers. What is left has reached exactly 0, so the chosen numbers add up to the target. A copy is stored because the one working list keeps changing as the search goes on.
4. Try each candidate from the start position until one is too large. Beginning at the start position means never going back to an earlier candidate, so each combination is built in one order only. A candidate larger than what is left would overshoot, and so would every later one.
5. Choose the candidate and go on from the same position. The next call gets the same position, not the one after it, because a candidate may be used again. What is left shrinks with every choice, so the calls cannot go on forever.
6. Take the candidate back before trying the next one. All the calls share one list of chosen numbers. Removing the candidate puts the list back exactly as this call found it, so the next candidate starts from the same numbers.
7. Start with nothing chosen and the whole target left. Position 0 allows every candidate, and nothing has been subtracted yet. When this first call returns, every combination has been recorded, and the list of answers is returned.

The same numbered steps are the comments in each solution.

function solve(candidates, target) {
  // 1. Sort a copy of the candidates and keep a list for the answers
  const nums = [...candidates].sort((a, b) => a - b),
    out = [];
  // 2. Extend the numbers chosen so far, from a start position
  function visit(start, left, path) {
    // 3. Nothing is left to add: record a copy of the chosen numbers
    if (left === 0) {
      out.push([...path]);
      return;
    }
    // 4. Try each candidate from the start position until one is too large
    for (let i = start; i < nums.length && nums[i] <= left; i++) {
      // 5. Choose the candidate and go on from the same position
      path.push(nums[i]);
      visit(i, left - nums[i], path);
      // 6. Take the candidate back before trying the next one
      path.pop();
    }
  }
  // 7. Start with nothing chosen and the whole target left
  visit(0, target, []);
  return out;
}

function solve(candidates: number[], target: number): number[][] {
  // 1. Sort a copy of the candidates and keep a list for the answers
  const nums = [...candidates].sort((a, b) => a - b),
    out: number[][] = [];
  // 2. Extend the numbers chosen so far, from a start position
  function visit(start: number, left: number, path: number[]): void {
    // 3. Nothing is left to add: record a copy of the chosen numbers
    if (left === 0) {
      out.push([...path]);
      return;
    }
    // 4. Try each candidate from the start position until one is too large
    for (let i = start; i < nums.length && nums[i] <= left; i++) {
      // 5. Choose the candidate and go on from the same position
      path.push(nums[i]);
      visit(i, left - nums[i], path);
      // 6. Take the candidate back before trying the next one
      path.pop();
    }
  }
  // 7. Start with nothing chosen and the whole target left
  visit(0, target, []);
  return out;
}

def solve(candidates, target):
    # 1. Sort a copy of the candidates and keep a list for the answers
    nums = sorted(candidates)
    result = []

    # 2. Extend the numbers chosen so far, from a start position
    def backtrack(start, left, path):
        # 3. Nothing is left to add: record a copy of the chosen numbers
        if left == 0:
            result.append(path.copy())
            return
        # 4. Try each candidate from the start position until one is too large
        for i in range(start, len(nums)):
            if nums[i] > left:
                break
            # 5. Choose the candidate and go on from the same position
            path.append(nums[i])
            backtrack(i, left - nums[i], path)
            # 6. Take the candidate back before trying the next one
            path.pop()

    # 7. Start with nothing chosen and the whole target left
    backtrack(0, target, [])
    return result

Example 1, traced

Input
candidates = [2,3,6,7]
target = 7

Output
[[2,2,3],[7]]

Why it works

The chosen numbers always add up to the target minus what is left, and they never go down. So a call with nothing left holds a real combination. Every combination, written from smallest to largest, is a path of choices the loops allow, so it is found. It is found once, because that order is the only one the search can build.

Time and space

Time Exponential in target / smallest candidate, extra space O(target / smallest candidate) stack plus output. Each chosen number is at least the smallest candidate, so a combination holds at most target ÷ smallest candidate numbers, and the calls nest about that deep. Each level can branch into several candidates, so the calls can grow exponentially with that depth. Space is that depth plus the answer.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Record a copy of the chosen numbers, not the list itself. Every stored entry would be the same shared list, which is empty again when the search ends: example 1 returns two empty lists.
• Start each loop at the position the call was given, not at the first candidate. From the first candidate, a combination is built once per order: example 1 returns [2, 2, 3], [2, 3, 2], [3, 2, 2] and [7].
• After choosing a candidate, pass on its own position, not the next one. With the next position every candidate can be used once only, and example 1 returns [7] alone.

Pattern

Backtracking. Builds on Generate Parentheses and Subsets.

Keep going