Backtracking · Choose, explore, undo

Medium · O(n^(T/m)) time · O(T/m) space

Problem

You are given an array of distinct positive integers candidates and a positive integer target. Return every unique combination of candidates that sums to target. You may use the same number as many times as you like. Two combinations are the same if they use each number the same number of times, so [2, 3] and [3, 2] count once. The combinations can come back in any order.
Example 1 Input: candidates = [2, 3, 5], target = 7 Output: [[2, 2, 3], [2, 5]] (2+2+3 = 7 and 2+5 = 7) Example 2 Input: candidates = [2], target = 1 Output: [] (2 is already larger than 1)
Constraints 1 ≤ candidates.length ≤ 30 2 ≤ candidates[i] ≤ 40, all distinct 1 ≤ target ≤ 40

Brute force

You have a list of numbers and a target. Find every way to add numbers from the list to reach the target. You may use the same number as many times as you like. For [2, 3, 5] and a target of 7, the answers are 2 + 2 + 3 and 2 + 5.

  1. Pick numbers so that they add up to exactly the target.
  2. A number can be picked again and again.
  3. Return every valid combination, not only one, and not only how many.
  4. Order does not matter: [2, 2, 3] and [3, 2, 2] are the same combination, and must appear once.

Because we must return every answer, we cannot avoid trying every option, so this is a search. At each step we make one decision: which number do we add next? Each decision shrinks the amount we still need. Here are the first decisions for [2, 3, 5] and target 7. The small number under each circle is what is still needed.

Each branch is one decision, and a path from the top is a partly built answer. It is finished when nothing is needed any more (the remaining amount reaches 0), and it is dead when the remaining amount would go below 0.

The direct idea: at every step try every number, stop when the sum reaches the target, and remove the repeats afterwards by sorting each answer and keeping it in a set.

The problem with it

It is correct, but it does the same work again and again. The combination {2, 2, 3} is reached as [2, 2, 3], as [2, 3, 2] and as [3, 2, 2], three different paths for one answer. With more numbers, the same answer is reached in many orders, and we throw all but one away at the end.

How to think your way to the optimal solution

We should never build the same combination in two orders. How can we make sure each combination is built in only one order?

Add a rule: numbers are added in the order they appear in the list. Once we have chosen a number, we may choose the same number again, or one that comes later in the list, but never one that comes earlier. We keep an index start that remembers "the earliest number we are still allowed to pick". With that rule, [2, 2, 3] can only be built as 2, then 2, then 3. The other orders would need a step backwards, and start forbids that.

One more trick: sort the list first. Then, once a number is too big for what we still need, every number after it is too big as well, so we can stop the loop with break, instead of checking each one.

This is backtracking: choose a number, explore what comes after, then undo the choice (remove the number) and try the next one.

The optimal solution

  1. Sort the numbers. Start with an empty path and call dfs(0, target).
  2. In dfs(start, remaining): remaining is 0⟶save a copy of the path and return
  3. For each index i from start: candidates[i] is more than remaining⟶stop the loop (all later ones are bigger too)
  4. Otherwise add the number to the path and call dfs(i, remaining − number). Use i, not i + 1, because the same number may be used again.
  5. When it returns, remove the number from the path (undo) and try the next index.

By hand, with [2, 3, 5] and target 7:

  1. Pick 2 (need 5), pick 2 again (need 3), pick 2 again (need 1). Now 2 is more than 1, so stop. Undo that last 2.
  2. At "need 3", try 3: need 0. Save [2, 2, 3]. Undo it. Try 5: too big, stop. Undo the second 2.
  3. At "need 5", try 3: need 2. Both 3 and 5 are more than 2, so stop. Undo. Try 5: need 0. Save [2, 5]. Undo.
  4. Undo the first 2. Pick 3 (need 4): 3 gives need 1, which fails; 5 is too big. Pick 5 (need 2): all too big. Done.

The answer is [[2, 2, 3], [2, 5]]. Press Play to watch the path grow and shrink.

Complexity analysis

O(nT/m)
Time. Here's why: n is the number of candidates, T is the target, and m is the smallest candidate. The deepest path uses the smallest number again and again, so it has at most T / m steps. Each step can choose from up to n numbers, so the number of paths is at most n to the power of T / m. In practice the sorting trick and the start rule cut away most of them.
O(T/m)
Space. The path and the nested calls are at most T / m deep. The list of answers is the output and is counted separately.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"The list can contain repeated numbers, and each number may be used only once."

What they are checkingWhether you can change a search that allows repeats into one that does not, and whether you know the duplicate trap. This is the well-known "Combination Sum II".

A strong answerTwo changes. First, I call dfs(i + 1, …) instead of dfs(i, …), so a number is never used twice. Second, because the list may hold equal numbers, I sort it and skip a number if it equals the one before it at the same level of choice. That stops me from building the same combination twice just because there are two equal numbers.

"I only want to know how many combinations there are."

What they are checkingWhether you notice that listing everything is much more work than counting, and that the problem becomes a different kind of problem.

A strong answerNow I do not need the combinations themselves, so I can use a table instead of a search, like the coin-change counting problem: ways[a] is the number of combinations that make a, with ways[0] = 1. The loop over the numbers goes on the outside and the loop over amounts on the inside, so that [2, 3] and [3, 2] are not counted as two ways. See Coin Change. That takes O(n × T) time instead of exponential time.

"Two bugs people make here: appending path instead of a copy, and forgetting the undo. What happens?"

What they are checkingWhether you understand that the path is one shared list that keeps changing.

A strong answerIf I append path itself, I save a reference to the same list, not its current contents. When the search carries on and the path changes, every saved answer changes with it, and at the end they are all empty. That is why I save path[:], a copy. If I forget the undo (path.pop()), numbers pile up in the path, so later branches start with leftover numbers and give wrong sums.

Spot this pattern