Combination Sum: Reuse the Number, Keep the Index

Generate Parentheses builds strings under two counters. Combination Sum, LeetCode 39, rated Medium, builds lists of numbers that add to a target. The skeleton is the same append-recurse-pop. The new idea is the start index: it is how you allow a candidate to be reused without listing the same combination in every order.

The trap is to treat this as Coin Change. Coin Change asks for the fewest coins. Combination Sum asks you to list every combination. One is a number. The other is a search tree you have to prune.

The Problem

Given distinct positive integers candidates and an integer target, return every combination of candidates that sums to target. You may reuse a candidate as many times as you want. Order does not matter: [2, 2, 3] and [3, 2, 2] are the same combination and must appear once.

Input:  candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]

[2, 5] is not an answer because 5 is not in the list. [2, 2, 2, 2] overshoots. An empty candidates list, or a target smaller than every candidate, returns [].

Recognizing the Backtracking Pattern

Backtracking is depth-first search on an implicit tree of partial answers. Each node is a path (the numbers chosen so far) and a remainder. At a node you try the next legal choice, recurse, then undo the choice so the sibling can use the same buffer.

Two rules keep the tree from exploding:

• Reuse without permuting. After you pick candidates[i], the next call is allowed to pick candidates[i] again, but it is not allowed to pick an earlier index. That forbids [2, 3] and [3, 2] as separate leaves. The start index is the whole encoding of "combinations, not permutations."
• Cut when the remainder dies. If the next value is larger than what is left, every later value is larger too once the array is sorted, so you break rather than keep walking.

If you restart the loop at index 0 on every call, you generate permutations. Interviewers watch for that. Saying "I pass i, not 0, and not i + 1" is the sentence that shows you own the problem rather than a template.

The Approach

Sort first so the prune is a break, not a hope. Keep a shared path and the remaining sum. Recurse. When the remainder is 0, snapshot a copy of the path. After each recursive call, pop.

Start the inner loop at start, not at 0. Recurse with i (same index: reuse is legal). Do not recurse with i + 1 unless the follow-up forbids reuse.

Copy on record (path.copy() or list(path)). The buffer keeps mutating. If you append the buffer itself, every result row aliases the same list and ends as [] after the last pop.

Python Solution

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """All combinations of distinct candidates that sum to target. Reuse allowed."""
    candidates = sorted(candidates)
    result: list[list[int]] = []
    path: list[int] = []

    def dfs(start: int, remaining: int) -> None:
        if remaining == 0:
            result.append(path.copy())
            return
        for i in range(start, len(candidates)):
            value = candidates[i]
            if value > remaining:
                break
            path.append(value)
            dfs(i, remaining - value)  # same index: this value may be reused
            path.pop()

    dfs(0, target)
    return result

The pop after each recursive call is the same restore used in Generate Parentheses and Path Sum II. Forget it and every path aliases one mutating buffer.

Sorting is not required for correctness on LeetCode 39 — the inputs are already distinct positives — but it makes the value > remaining cut valid. Without a sort you must continue, not break, and you explore branches you could have skipped.

Walkthrough for [2, 3, 6, 7], target = 7

Sorted already. Start at (start=0, remaining=7), path empty.

• Pick 2. Remainder 5. Stay at index 0.
  • Pick 2. Remainder 3.
    • Pick 2. Remainder 1. Next value 2 is already too big. Dead.
    • Pick 3. Remainder 0. Record [2, 2, 3].
    • 6 and 7 overshoot.
  • Pick 3 from remainder 5. Remainder 2. Next legal start is 3, which is already too big. Dead. This is why [2, 3, 2] never appears: after picking 3 you are not allowed to go back to 2.
  • 6 and 7 overshoot remainder 5.
• Pick 3 from the root. Remainder 4. Start index is now 1, so 2 is gone. 3 leaves 1, then everything overshoots. Dead.
• Pick 6. Remainder 1. Dead.
• Pick 7. Remainder 0. Record [7].

Two leaves. The permutation [3, 2, 2] was never a node. Draw this if they hand you a marker: the first number in a combination is non-decreasing along the path.

Complexity

• Time: exponential in target / min(candidates). Each path can grow until the remainder hits zero or goes negative, and at every step you have a linear number of choices that still fit. Sorting is O(n log n) and does not dominate. You cannot beat the size of the output; the output is the list of combinations.
• Space: O(target / min(candidates)) for the path and the call stack, plus whatever the result list occupies. Do not count the output against the algorithm unless they ask you to.

LeetCode keeps candidates.length small and target small, so the search finishes. The reason to name the bound is to show you know this is not O(n) and not "DP in disguise that happens to list things."

The permutation answer they are waiting to reject

# Do not ship this. It lists every order of the same multiset.
def combination_sum_permuted(candidates: list[int], target: int) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def dfs(remaining: int) -> None:
        if remaining == 0:
            result.append(path.copy())
            return
        for value in candidates:          # always from the front
            if value > remaining:
                continue
            path.append(value)
            dfs(remaining - value)
            path.pop()

    dfs(target)
    return result

For [2, 3] and target 5 this emits [2, 3] and [3, 2]. The start index is what deletes the second one. If they ask "why not start at zero," say uniqueness of combinations, not "it is slower." Slow is a symptom. Exploring both orders is the cause.

The dynamic-programming cousin is Coin Change: same unlimited reuse, but dp[amount] stores a count, not a path. Use DP when they want a number. Use backtracking when they want the lists. Coin Change II (LeetCode 518) wants the count of combinations; that is a DP table indexed by amount, not this search.

Interview Tips and Follow-Ups

• Empty input. candidates = [] or target = 0. Ask. Target 0 is one empty combination if you record at the top of dfs before the loop; LeetCode's constraints start target at 1, so they are probing whether you clarify.
• Combination Sum II (LeetCode 40). Candidates may contain duplicates. Each value may be used at most once. Recurse with i + 1, and skip a duplicate at the same depth: if i > start and candidates[i] == candidates[i - 1]: continue. Skipping across depths would drop a valid [1, 1, 6].
• Combination Sum III (LeetCode 216). Choose exactly k numbers from 1..9. The start index is the same; add if len(path) == k as the success test next to remaining == 0.
• Permutations (LeetCode 46). Drop the start index. Track a used boolean (or swap in place). Order now matters, so [1, 2] and [2, 1] are both answers.
• Subsets (LeetCode 78). Every node is an answer, not only the leaves that hit a target. Recurse with i + 1 twice: once after appending candidates[i], once without. No remainder.
• Can you DP the lists? You can, with dp[amount] holding every combination that sums to amount. It uses more memory than the recursive search, and you still have to copy lists. Offer it if they ask; do not start there.

Combination Sum is Generate Parentheses with a numeric remainder: the prune is value > remaining, and the uniqueness invariant is the start index instead of two counters. Same append-recurse-pop. More of that family sits in the Technical Interview category.