Combination Sum: Backtracking with Reuse

Given an array of distinct integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. You may use the same number an unlimited number of times.

This is LeetCode 39: Combination Sum, and it is one of the best problems for understanding how a single tweak to the backtracking template creates a completely different problem. If you have already solved Subsets or Permutations, you know the choose-explore-unchoose skeleton. Combination Sum uses that exact same skeleton, but with one critical difference: you are allowed to reuse elements. That one change turns a subset enumeration into a constrained search with pruning.

Why this problem matters

Combination Sum sits right at the intersection of backtracking and pruning. Most pure backtracking problems (Subsets, Permutations) enumerate everything without cutting branches. Combination Sum forces you to prune: if the running sum already exceeds the target, there is no reason to keep exploring. This is the first time many people encounter the idea of short-circuiting a recursion tree based on a constraint.

It also teaches you how "reuse allowed" changes the recursion. In Subsets, you recurse with i + 1 so you never reconsider an element. In Combination Sum, you recurse with i (not i + 1) so the same element can be picked again. That single index change is the entire difference between "each element used at most once" and "unlimited reuse." Once you see that, a whole family of problems clicks into place.

Finally, sorting the candidates unlocks an optimization: once a candidate exceeds the remaining target, every candidate after it will too (since the array is sorted). You can break out of the loop instead of continuing, which prunes entire subtrees in one shot.

The key insight

Think of building a combination as a sequence of additions. At each step you ask: "Which candidate do I add next?" You can add the same candidate again, but to avoid duplicates like [2,3,2] and [2,2,3], you only consider candidates at or after the current index. This "start index" trick is identical to what Subsets uses, except you pass i instead of i + 1 when you recurse.

The algorithm works like this:

1. Sort the candidates (this enables pruning).
2. Start with an empty combination, remaining = target, and start index 0.
3. If remaining is 0, the current combination sums to the target. Record it.
4. For each candidate from the start index onward, if the candidate exceeds remaining, break (all later candidates are bigger, so they will also exceed it).
5. Otherwise, choose the candidate (append it), explore (recurse with the same start index and reduced remaining), and unchoose (pop it).

The backtracking solution

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    result = []

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

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # pruning: sorted, so all later candidates are too big

            current.append(candidates[i])          # choose
            backtrack(i, remaining - candidates[i], current)  # explore (i, not i+1)
            current.pop()                           # unchoose

    backtrack(0, target, [])
    return result

Let's break this down.

The outer function sorts the candidates first. Sorting is not strictly required for correctness, but it enables the break optimization. Without sorting, you would need continue instead of break, and you would check every candidate even when most of them are too large.

Inside backtrack, the base case is remaining == 0. When the running sum hits the target exactly, we copy the current combination and add it to the result.

The for loop iterates from start to the end of the candidates array. For each candidate, we first check if it exceeds the remaining sum. If it does, we break out of the loop. Since the array is sorted, every candidate after this one is at least as large, so none of them can work either. This is the pruning step, and it prevents the algorithm from exploring entire subtrees that can never produce a valid combination.

If the candidate fits, we append it (choose), recurse with the same index i and a reduced remaining (explore), and then pop it off (unchoose). Passing i instead of i + 1 is the key difference from Subsets. It means "this same candidate is still available for the next recursive call." That is what allows unlimited reuse.

Visual walkthrough

Let's trace through the algorithm with candidates = [2, 3, 6, 7] and target = 7. Watch how pruning cuts off branches early and how reuse lets us pick the same candidate multiple times.

Notice how the pruning kicks in at step 4: when remaining = 1, every candidate (2, 3, 6, 7) exceeds it, so the entire subtree is abandoned. At step 6, candidates 6 and 7 both exceed remaining = 3, so those branches are pruned too. Without pruning, the tree would be much deeper and wider. With sorted candidates and the break optimization, large chunks of the tree are never explored.

How this differs from Subsets

The comparison is worth spelling out explicitly, because the code looks almost identical:

In Subsets, every partial combination is a valid answer, so you record at every recursive call. In Combination Sum, only combinations that hit the target exactly are valid, so you record only at the base case. Subsets explores the full tree; Combination Sum prunes aggressively.

If you are comfortable with Subsets, Combination Sum is a small step. You add a remaining parameter, change i + 1 to i, and add a pruning check. The skeleton is the same.

Complexity analysis

Time is hard to pin down exactly. In the worst case, the recursion tree can have up to O(n^(T/M)) nodes, where n is the number of candidates, T is the target, and M is the smallest candidate. This is because at each level you have up to n choices, and the maximum depth is T/M (you keep adding the smallest candidate until you hit the target). In practice, pruning makes it much faster, but the worst case is exponential.

Space is O(T/M) for the recursion stack (the maximum depth of the tree) plus the space for storing results. The recursion depth is at most T/M because each level adds at least M to the running sum.

Edge cases

Before submitting, check these:

• Target equals a candidate: candidates = [7], target = 7. Should return [[7]]. One element, one combination.
• No valid combinations: candidates = [3], target = 2. Should return []. The smallest candidate exceeds the target.
• Single candidate, multiple uses: candidates = [2], target = 4. Should return [[2, 2]]. Same element used twice.
• Large target, small candidates: Can create deep recursion trees. The pruning keeps it manageable, but be aware that the number of results can grow quickly.

The building blocks

This problem is built on one core reusable piece that CodeBricks drills independently.

Choose-explore-unchoose (backtracking template)

The same skeleton that powers Subsets, Permutations, and Word Search:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)      # choose
        backtrack(state)          # explore
        undo_choice(choice)       # unchoose

In Combination Sum, make_choice is current.append(candidates[i]). backtrack recurses with the same i and remaining - candidates[i]. undo_choice is current.pop(). The pruning (break when candidate > remaining) is an optimization layered on top of this template.

This same template handles:

• Combination Sum II (LeetCode 40): change i to i + 1 and skip consecutive duplicates.
• Subsets (LeetCode 78): change i to i + 1 and record at every node instead of only when remaining == 0.
• Permutations (LeetCode 46): iterate over all unused elements instead of from a start index.
• N-Queens (LeetCode 51): the choice is which column to place the queen in each row.

The choose-explore-unchoose pattern is the skeleton. Each problem just plugs in different candidates, constraints, and base cases.

Common mistakes

1. Not sorting the candidates. Without sorting, the break optimization does not work. You can still solve the problem with continue instead of break (skip candidates that are too large), but you lose the ability to prune entire subtrees. Sorting costs O(n log n) and pays for itself many times over.

2. Passing i + 1 instead of i. This is the most common bug. If you pass i + 1, each element can only appear once per combination. You will miss results like [2, 2, 3] because after picking 2, the next call starts at 3. Always pass i for unlimited reuse.

3. Forgetting to copy before recording. Just like in Subsets and Permutations, result.append(current) appends a reference. After all the pop() calls, current is empty, and every entry in your result is []. Use current[:] or list(current).

4. Not pruning (or using continue instead of break). Without the break, the algorithm still produces correct results, but it wastes time checking candidates that are guaranteed to be too large. With sorted candidates, break exits the loop immediately when a candidate exceeds the remaining target.

When to use this pattern

Look for these signals:

• The problem asks for all combinations that sum to a target
• Elements can be reused an unlimited number of times
• You need to find all valid selections, not just a count or a single one
• Constraints mention a small target value or small candidate list (hinting at backtracking)

Problems that use the same backtracking with reuse pattern:

• Combination Sum II (LeetCode 40): same structure but each element used at most once, plus duplicate handling
• Combination Sum III (LeetCode 216): k numbers from 1-9 that sum to n, each used once
• Coin Change (LeetCode 322): same "reuse allowed" idea, but asks for the minimum count instead of all combinations (solved with DP, not backtracking)

From understanding to recall

You understand the recursion tree. You see how passing i instead of i + 1 enables reuse, and how the break prunes entire branches when a sorted candidate exceeds the remaining target. But can you write the combination sum LeetCode solution from scratch in under two minutes?

That is what interviews demand. Backtracking with reuse looks simple in a blog post, but under pressure, small details trip people up: passing the wrong index, forgetting to sort, using continue instead of break, forgetting to copy the list. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the choose-explore-unchoose template and the combination-sum-specific loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "combination sum LeetCode" and the code flows out without hesitation.

The choose-explore-unchoose pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Subsets - The simplest backtracking problem using the same choose-explore-unchoose template. Compare it to Combination Sum to see how i + 1 vs i changes the problem from "enumerate all" to "reuse allowed."
• Permutations - Another backtracking problem using the same template. Shows how the same skeleton adapts when order matters and every element must appear exactly once.
• Coin Change - Same "unlimited reuse" idea, but solved with dynamic programming instead of backtracking. Useful contrast for understanding when to enumerate all results vs. optimize for a single value.

CodeBricks breaks Combination Sum into its choose-explore-unchoose building block, then drills it independently with spaced repetition. You type the backtracking skeleton from scratch until it is automatic. When a backtracking problem shows up in your interview, you do not think about it. You just write it.