Combination Sum

Combination Sum is the gateway to backtracking — building every valid combination by making a choice, recursing, then undoing it. The twist here is that you may reuse a candidate as many times as you want.

The slow way first

You might try generating every possible multiset of numbers and checking which ones sum to the target. But the number of multisets is enormous, and most of them blow past the target. Brute force has no way to stop early, so it explores a gigantic space pointlessly.

The fix is to build combinations incrementally and abandon a path the instant it can no longer succeed. That is backtracking.

The idea: choose, recurse, undo

We keep a running total and a path (the numbers chosen so far). At each step we loop over the candidates and try adding one:

• If total + v overshoots the target, skip it — prune that branch.
• Otherwise add v to the path and recurse. Crucially, we recurse with start index i, not i + 1, so the same number can be picked again.
• When total == target, we found a valid combination — collect a copy of the path.
• After exploring, we pop v back off the path so the next choice starts clean.

Passing start (and only ever increasing it across the loop, never resetting it for the recursion) is what stops us from producing the same combination in a different order — we only ever extend with candidates at index i or later.

Walk through it

Step through the animation. Each tree node shows the running sum; each edge adds a candidate. We dive 2 → 2 → 2 to reach sum 6, then adding another 2 would make 8, so that branch turns red and is pruned. We backtrack and add 3 instead: 2 + 2 + 3 = 7, a hit — collect [2, 2, 3]. Unwinding to the root, picking 7 lands on the target directly: collect [7]. The result is [[2, 2, 3], [7]].

Pseudocode

result = []
backtrack(start, total, path):
    if total == target:
        add a COPY of path to result
        return
    for i from start to end of candidates:
        v = candidates[i]
        if total + v > target:
            continue            # prune: this choice overshoots
        path.append(v)
        backtrack(i, total + v, path)   # i (not i+1) -> v can repeat
        path.pop()              # undo the choice
backtrack(0, 0, [])

The Python solution

def combination_sum(candidates, target):
    result = []
 
    def backtrack(start, total, path):
        if total == target:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            v = candidates[i]
            if total + v > target:
                continue                  # prune: overshoot
            path.append(v)
            backtrack(i, total + v, path)  # i, not i + 1 -> reuse
            path.pop()                    # undo (backtrack)
 
    backtrack(0, 0, path=[])
    return result

• path[:] stores a copy — path keeps mutating, so we must snapshot it when we collect.
• The if total + v > target: continue line is the prune; because candidates are positive, once you overshoot, adding more can never come back.
• backtrack(i, ...) passes i, not i + 1 — that single character is what allows reusing a candidate.
• path.pop() is the undo that makes this backtracking: after exploring a choice fully, we remove it so the next loop iteration starts from the same state.

Complexity

The bound is exponential in the worst case — backtracking explores a tree — but pruning overshoots keeps the real work far smaller. Space is the recursion depth plus the current path, both at most T/M.

When this pattern shows up

Practice