Combination Sum

Combination Sum is where backtracking starts to prune. The target gives you a budget, and a branch that has spent more than the budget is dead. Sorting the candidates turns that into a break that cuts off a whole row of branches at once.

It also shows the most important one-token change in the pattern: passing i instead of i + 1, so a number may be chosen again.

The problem

You are given a list of distinct positive integers, candidates, and a positive target. Return every combination of candidates that adds up to the target. You may use the same number as many times as you like. Two combinations are the same if they use the same numbers the same number of times, in any order — return each only once.

• candidates = [3, 4, 5], target = 11 → [[3, 3, 5], [3, 4, 4]]. 3 + 3 + 5 = 11 and 3 + 4 + 4 = 11; nothing else works.
• candidates = [4], target = 3 → []. The only coin is already too big.

Constraints: 1 ≤ n ≤ 30, candidates between 2 and 40, all distinct, 1 ≤ target ≤ 40.

Clarifying questions

• Can a number be reused? Yes, any number of times. (The follow-up removes this.)
• Are [3, 4, 4] and [4, 3, 4] different? No — one combination, returned once.
• Can candidates be zero or negative? No. A zero would allow endless combinations, and negatives would break the "too big, stop" prune.
• No combination? Return an empty list.

Approach 1: the simple way — try every number at every step

At each step, add any candidate and recurse on the rest of the target. When the rest hits 0, sort the path and put it in a set, so [3, 4, 4] and [4, 4, 3] count once.

1def combination_sum_brute(candidates: list[int], target: int) -> list[list[int]]:2    """Try every candidate at every step, then de-duplicate with a set."""3    found: set[tuple[int, ...]] = set()4    path: list[int] = []56    def build(remaining: int) -> None:7        if remaining == 0:8            found.add(tuple(sorted(path)))9            return10        if remaining < 0:11            return12        for c in candidates:13            path.append(c)14            build(remaining - c)15            path.pop()1617    build(target)18    return [list(t) for t in found]

Why it is too slow. It builds every ordering of every combination and then throws the copies away. For [3, 4, 5] and 11 it makes 52 calls to find 2 answers. For [2, 3, 5, 7] and target 30 it makes 264,453 calls to find 45 combinations. It also goes one step past the target on every branch before it notices.

The key insight

Build each combination in one fixed order only: non-decreasing index. Once you have chosen candidate i, you may choose i again or anything after it, but never something before it. Then [3, 4, 4] can be built, but [4, 3, 4] never can, so no set is needed.

That is the Subsets start index with one change. Subsets passes i + 1 ("move past this one"). Here we pass i ("this one again is fine"). Reuse is allowed, repeats in the output are not.

The second insight is the prune. Sort the candidates. If candidates[i] is bigger than what is left of the target, every candidate after it is bigger too, so break — not continue — ends the whole loop at once.

Approach 2: start index plus sorted break

1def combination_sum(candidates: list[int], target: int) -> list[list[int]]:2    """Every combination (reuse allowed) of distinct candidates summing to target."""3    candidates = sorted(candidates)4    result: list[list[int]] = []5    path: list[int] = []67    def backtrack(start: int, remaining: int) -> None:8        if remaining == 0:9            result.append(path[:])           # hit the target exactly10            return11        for i in range(start, len(candidates)):12            if candidates[i] > remaining:13                break                        # sorted: everything after is too big too14            path.append(candidates[i])15            backtrack(i, remaining - candidates[i])   # i, not i + 1: reuse allowed16            path.pop()1718    backtrack(0, target)19    return result

The state is (start, remaining): where the loop may begin, and how much of the target is still unpaid. The finish rule is remaining == 0. There is no "went below 0" case, because the break stops that before the call is made.

Dry run on [3, 4, 5], target 11. Each row is one call:

Fourteen calls instead of 52, and the answer [[3, 3, 5], [3, 4, 4]] comes out with no set. On [2, 3, 5, 7] and 30 the gap is 446 calls against 264,453.

Complexity. Let T be the target and m the smallest candidate. The path is at most T / m long, and each node has at most n children, so the tree has O(n^(T/m)) nodes in the worst case, and each recorded answer costs O(T/m) to copy. This bound is loose — the break cuts most of it — and saying so is the honest answer. Working space is O(T / m) for the recursion.

Each number at most once, with repeats (Combination Sum II)

Change the rules: each position in candidates may be used at most once, and candidates may contain repeated values. Example: [1, 2, 2, 2, 5], target 5 → [[1, 2, 2], [5]].

Two changes, both from earlier lessons. Pass i + 1 so a position is not reused. And skip a value equal to the one just tried in the same loop — the i > start rule from Subsets — so the three 2s do not produce [1, 2, 2] three times.

1def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:2    """Each position used at most once; no duplicate combinations."""3    candidates = sorted(candidates)4    result: list[list[int]] = []5    path: list[int] = []67    def backtrack(start: int, remaining: int) -> None:8        if remaining == 0:9            result.append(path[:])10            return11        for i in range(start, len(candidates)):12            if i > start and candidates[i] == candidates[i - 1]:13                continue                     # same value, same loop: skip14            if candidates[i] > remaining:15                break16            path.append(candidates[i])17            backtrack(i + 1, remaining - candidates[i])   # i + 1: no reuse18            path.pop()1920    backtrack(0, target)21    return result

In the root loop, the first 2 is tried and the next two 2s are skipped. Inside the branch [1], the loop starts at the first 2, takes it, and its child starts at the second 2 with i == start, so [1, 2, 2] is still built — once.

Edge cases

• Smallest candidate bigger than the target — the root loop breaks on its first step; the answer is [].
• Target equal to one candidate — [candidate] is recorded one level down.
• Unsorted input — the break is only correct after sorting. Without the sort it would cut off smaller candidates that come later.
• Many small candidates and a big target — the depth grows to T / m; with m ≥ 2 and T ≤ 40, depth stays at 20 or less.

Follow-ups

• Exactly k numbers from 1 to 9, each once (Combination Sum III) — the same loop over 1..9 with i + 1, and record only when both len(path) == k and the remaining sum is 0.
• Only the number of combinations — do not list them. That is Coin Change II, a dynamic programming count in O(n × T) time (see the Dynamic Programming section).
• Different orders count as different (Combination Sum IV) — the answer count explodes, so again switch to dynamic programming, looping the target on the outside.