4.18.2 — Combination Sum

LeetCode 39 · Medium · ★ Blind 75

The problem

Given distinct positive numbers and a target, return every combination summing to the target. Each number may be used any number of times. Two combinations are different only if the counts differ, so [2,2,3] and [3,2,2] are the same answer and only one should appear.

candidates = [2,3,6,7], target = 7   →  [[2,2,3], [7]]
candidates = [2],       target = 1   →  []

All candidates are at least 2, which matters — see below.

The pattern

This is 4.18.1 Subsets's start-index loop with one character changed.

backtrack(i + 1, ...)     # subsets: each element used at most once
backtrack(i, ...)         # here:    the same element may be reused

Passing i instead of i + 1 means the loop can pick the same candidate again on the next level. Passing start at all — rather than looping from 0 — is what stops [3,2,2] appearing as well as [2,2,3]: the walk only ever moves forward through the candidate list, so each combination is generated in one fixed order.

Those two facts are the whole solution. Everything else is pruning.

The pruning

Two conditions end a branch:

• The running sum equals the target — record it and stop. Adding more can only overshoot, because all candidates are positive.
• The running sum exceeds the target — abandon it. Same reason.

Both of these depend on all candidates being positive. With negatives allowed, a sum that has overshot could come back down, so neither cut would be safe and the search space would be infinite with reuse permitted. Say this if asked — it is the assumption doing the work.

Sorting the candidates first buys one more cut: once candidates[i] alone exceeds what remains, every later candidate does too, so you can break out of the loop instead of continue. That turns "skip this branch" into "skip all remaining branches".

The solution

Python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()                    # enables the break below
        result = []
        path = []

        def backtrack(start: int, remaining: int):
            if remaining == 0:
                result.append(path[:])
                return

            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break                    # sorted → everything after is worse

                path.append(candidates[i])
                backtrack(i, remaining - candidates[i])    # i, NOT i + 1
                path.pop()

        backtrack(0, target)
        return result

TypeScript

function combinationSum(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => a - b);
  const result: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;

      path.push(candidates[i]);
      backtrack(i, remaining - candidates[i]);
      path.pop();
    }
  }

  backtrack(0, target);
  return result;
}

Counting down with remaining rather than up with a running total. Both work; counting down makes the base case a single comparison against zero and makes the pruning check read naturally.

break, not continue. Because the list is sorted, the first candidate too large for the remaining budget guarantees every later one is too. This is the difference between pruning one branch and pruning all the rest.

backtrack(i, ...). The line that allows reuse. Changing it to i + 1 gives you Combination Sum II's structure — see 4.18.5.

Trace

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

Start with 2, remaining 5. Take 2 again, remaining 3. Take 2 again, remaining 1 — now every candidate exceeds 1, so break, and this branch dies. Back up: from remaining 3, take 3 → remaining 0 → record [2,2,3] ✓.

Back up further: from remaining 5 take 3 → remaining 2, but start is now at index 1 so 2 is no longer reachable, and 3 > 2 so break. Dead.

Then 6 > 5 at the top level, break. Finally the branch starting at 7 gives remaining 0 → record [7] ✓.

Notice how the start index is what stops [3,2,2] from ever being built.

Complexity

Hard to state tightly, and saying so honestly is better than inventing a bound. The usual expression is O(n^{T/m}) where T is the target and m is the smallest candidate — because the deepest a path can go is T/m levels, with up to n branches at each.

For the real answer, say: "the search tree is bounded by depth target / smallest candidate with branching factor n, and the pruning cuts most of it; the output itself can be exponential."

Space is O(T/m) for the recursion depth.

Why the candidates must be positive

Two things break with a zero or a negative in the list:

• A zero could be added infinitely often without changing the sum, so the recursion never terminates.
• A negative means an overshoot can come back, so remaining < 0 is no longer a safe reason to abandon a branch.

The constraint "all candidates ≥ 2" is not decoration. Noticing which constraint makes your pruning legal is a habit worth building — the same reasoning that makes a sliding window valid in 4.6.

Where this goes next

• Combination Sum II — each number used once, and the input has duplicates. Two changes: i + 1, and the sorted duplicate skip. 4.18.5.
• Combination Sum III — exactly k numbers, drawn from 1 to 9. Add a length check to the base case.
• Combination Sum IV — despite the name, this is not a backtracking problem. It counts permutations and only asks for the count, so enumerating is far too slow and the answer is 1-D DP. 4.23. The name is a deliberate trap, and the tell is that it asks how many rather than which.
• Coin Change — the fewest coins reaching a target. Same shape, but you want one optimal answer rather than all answers, so it is DP.

The dividing line worth memorising: enumerate when you need every answer; use DP when you need a count or an optimum.

What the interviewer will push on

"Why i and not i + 1?" Reuse is allowed.

"Why does the loop start at start rather than 0?" So each combination is generated in one fixed order, which is how duplicates like [3,2,2] are prevented.

"Where is the pruning?" The break on a sorted list, and the remaining == 0 base case.

"What if candidates could be negative or zero?" The pruning becomes invalid and the recursion may not terminate.

"What if you only needed the number of combinations?" Switch to DP — enumerating is wasted work when you never look at the combinations themselves.

One thing to volunteer: say that this is the subsets template with i instead of i + 1. Naming the minimal difference from a problem you already solved is the fastest way to show you have a method.

Next: 4.18.3 Permutations — the third loop shape, where order matters and the start index disappears.