Combination Sum II

The problem

You are given a list of positive integers candidates, which may hold the same value more than once, and a positive integer target. Return every distinct combination of candidates that adds up to target. Each item of the list may be used at most once in a combination, so a value that appears twice may be used twice. Two combinations with the same numbers in a different order are the same combination and must be listed once. The combinations, and the numbers inside each one, may come in any order. If no combination works, return an empty list.

What to write

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

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

Output
[[1,1,6],[1,2,5],[1,7],[2,6]]

Input
candidates = [2,5,2,1,2]
target = 5

Output
[[1,2,2],[5]]

Constraints

Candidates and target are positive integers.

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 sum larger, and nothing can bring it back down. Once a sum is larger than target, no further number can fix it. Note also that a value can appear several times in candidates, and each appearance can be used once.

2. Hint 2: Ask a smaller question

   Take the candidates 1, 2, 2 and a target of 3. You can reach 3 with the 1 and the first 2, or with the 1 and the second 2. The answer lists [1, 2] once. Working by hand, how would you notice that the second way is a repeat before you finish building it?

3. Hint 3: Name the pattern

   You must list every combination, and each one is the result of a series of choices: which number comes next? That signals backtracking: choose a number, search on with what is left of target, then undo the choice and try another. Sorting first puts equal values side by side, so a repeated choice is easy to spot. Read the lesson on backtracking.

4. Hint 4: State the invariant

   In every call, the chosen numbers come from increasing positions of the sorted list, and they add up to target minus the amount left. Within one loop, no value is chosen twice: of several equal candidates in a row, only the first is chosen.

5. Hint 5: Sketch the pseudocode

   Sort candidates. search(start, left): if left is 0, save a copy of the chosen numbers and return. For i from start: if candidate i is larger than left, stop the loop. If i > start and candidate i equals the candidate before it, skip it. Otherwise add it, call search(i + 1, left minus it), remove it. Start: search(0, target).

Solution

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

Approach

Sort, advance the index after each choice, skip duplicate sibling choices, and stop when candidates exceed the remaining target.

The slow way

Try every way of picking some of the candidates. With n candidates there are 2^n ways. Add each one up and keep those that reach the target. It misses nothing, but it keeps building sums that are already too large, and when a value repeats it finds the same combination several times, so you would also have to remove the copies.

The insight

Build a combination one number at a time, smallest first, from a sorted list. Then two shortcuts appear. When a candidate is larger than the amount still missing, all later ones are too, so you can stop looking. And equal values sit side by side, so for the same place in a combination you try a value once and skip its copies.

Step by step

1. Sort the candidates so that equal values sit side by side. Sorted, a repeat is found by one comparison with the neighbor before it. Sorted order also means that once one candidate is too large, all the later ones are too.
2. Keep the combinations found and the one being built. One list collects the answers. The other holds the numbers chosen so far, and it grows and shrinks as the search goes forward and comes back.
3. Nothing is left to reach: save a copy of the chosen numbers. The amount left is the target minus the chosen numbers, so at 0 they add up to the target exactly. A copy is saved because the working list keeps changing afterwards.
4. Go through the candidates after the last choice; stop at one too large. Looking only after the last choice keeps an item from being used twice. With nothing chosen yet, the loop covers every candidate. A candidate larger than the amount left cannot fit, and neither can any later one.
5. Skip a candidate equal to the one before it in this loop. An equal candidate was already chosen earlier in this loop, and every combination that continues with this value was found then. Choosing it again would build the same combinations a second time.
6. Choose the candidate, search on from the next one, then take it back. The search that follows may only use later candidates, so this one is not used again. Taking it back afterwards leaves the chosen numbers as they were, ready for the next candidate of the loop.
7. Start with nothing chosen and the whole target left to reach. Every combination grows from this empty start. When the first call returns, every choice has been tried and taken back, so the list of answers is complete and is returned.

The same numbered steps are the comments in each solution.

function solve(candidates, target) {
  // 1. Sort the candidates so that equal values sit side by side
  candidates.sort((a, b) => a - b);
  // 2. Keep the combinations found and the one being built
  const out = [],
    path = [];
  function visit(start, left) {
    // 3. Nothing is left to reach: save a copy of the chosen numbers
    if (left === 0) {
      out.push([...path]);
      return;
    }
    // 4. Go through the candidates after the last choice; stop at one too large
    for (let i = start; i < candidates.length && candidates[i] <= left; i++) {
      // 5. Skip a candidate equal to the one before it in this loop
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      // 6. Choose the candidate, search on from the next one, then take it back
      path.push(candidates[i]);
      visit(i + 1, left - candidates[i]);
      path.pop();
    }
  }
  // 7. Start with nothing chosen and the whole target left to reach
  visit(0, target);
  return out;
}

function solve(candidates: number[], target: number): number[][] {
  // 1. Sort the candidates so that equal values sit side by side
  candidates.sort((a, b) => a - b);
  // 2. Keep the combinations found and the one being built
  const out: number[][] = [],
    path: number[] = [];
  function visit(start: number, left: number): void {
    // 3. Nothing is left to reach: save a copy of the chosen numbers
    if (left === 0) {
      out.push([...path]);
      return;
    }
    // 4. Go through the candidates after the last choice; stop at one too large
    for (let i = start; i < candidates.length && candidates[i] <= left; i++) {
      // 5. Skip a candidate equal to the one before it in this loop
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      // 6. Choose the candidate, search on from the next one, then take it back
      path.push(candidates[i]);
      visit(i + 1, left - candidates[i]);
      path.pop();
    }
  }
  // 7. Start with nothing chosen and the whole target left to reach
  visit(0, target);
  return out;
}

def solve(candidates, target):
    # 1. Sort the candidates so that equal values sit side by side
    candidates.sort()
    # 2. Keep the combinations found and the one being built
    result = []
    path = []

    def backtrack(start, left):
        # 3. Nothing is left to reach: save a copy of the chosen numbers
        if left == 0:
            result.append(path.copy())
            return
        # 4. Go through the candidates after the last choice; stop at one too large
        for i in range(start, len(candidates)):
            if candidates[i] > left:
                break
            # 5. Skip a candidate equal to the one before it in this loop
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            # 6. Choose the candidate, search on from the next one, then take it back
            path.append(candidates[i])
            backtrack(i + 1, left - candidates[i])
            path.pop()

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

Example 2, traced

Input
candidates = [2,5,2,1,2]
target = 5

Output
[[1,2,2],[5]]

Why it works

Written smallest first, every combination is one path of choices, and the search follows every such path: at each point it tries each distinct value that still fits. So nothing is missed. Nothing is listed twice either. The values chosen inside one loop are all different, so two different paths build two different combinations.

Time and space

Time O(n · 2^n), extra space O(n + output). Each of the n candidates is chosen or not, so there are at most 2^n calls. A call scans up to n candidates or copies up to n numbers: O(n · 2^n) time. Chosen numbers and unfinished calls take about n slots, plus the saved answers: O(n + output) space.

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

• Skip a repeat only when it is not the first candidate of its loop. If you compare with the neighbor at every position, a value can never follow its own copy, and example 2 returns only [5].
• Search on from the next position, not from the same one. From the same position an item is chosen again and again, and example 2 also returns [1, 1, 1, 2] and [1, 1, 1, 1, 1].
• Do not forget to sort: the early stop and the neighbor test both need sorted order. Unsorted, example 1 looks at 10 first, which is larger than 8, so the loop stops at once and the result is empty.

Pattern

Backtracking. Builds on Combination Sum and Subsets II.

Keep going