Combination Sum

Treat this as an enumeration problem, not a permutation problem. Sort the candidates, keep combinations in nondecreasing order, recurse from the same index to allow reuse, and carry the remaining target as the search state.

Given candidates = [2, 3, 6, 7] and target = 7, the result is:

[[2, 2, 3], [7]]

The combinations may be returned in any order. But inside each combination, [2, 2, 3], [2, 3, 2], and [3, 2, 2] represent the same frequency pattern. A correct search should generate that pattern once rather than produce every ordering and clean up the duplicates afterward.

Read the Contract and Name the Real Constraints

The problem gives us distinct, positive candidate values. Each value may be selected any number of times. We must return every unique combination whose sum equals target.

Those conditions determine the algorithm:

• Distinct candidates mean we do not need to handle duplicate values in the input.
• Unlimited reuse means choosing a candidate does not remove it from future consideration.
• Order-insensitive output means [2, 3] and [3, 2] are one result.
• Positive values mean a partial sum only increases as we extend a path. Once we overshoot the target, that branch cannot recover.
• Bounded target makes exhaustive enumeration practical for the given contract, even though the general search is exponential.

The immediate design is therefore:

1. Sort candidates.
2. Track the current path.
3. Track a start index so future choices cannot move backward.
4. Track remaining, the sum still needed.
5. Recurse with the same index after choosing a candidate, because reuse is allowed.
6. Stop when a candidate exceeds remaining.

This is the core Combination Sum solution. The rest is making each rule precise.

Why Permutation-Style Search Wastes Work

A tempting baseline is to choose any candidate at every level:

choose 2
  choose 2
    choose 3
choose 2
  choose 3
    choose 2
choose 3
  choose 2
    choose 2

For a target of 7, this can discover:

[2, 2, 3]
[2, 3, 2]
[3, 2, 2]

All three have the same frequencies: two copies of 2 and one copy of 3. Generating them is wasted work. Filtering afterward is also the wrong place to solve the problem. The search tree already knows that order does not matter, so the tree should enforce one order from the beginning.

Use a canonical nondecreasing order:

2, 2, 3

Once a branch chooses the candidate at index i, later choices may use index i again or move to a larger index. They may never choose an earlier index.

This rule does two jobs at once:

• Staying at i allows unlimited reuse.
• Never moving below i prevents reordered duplicates.

There are two common ways to express the recursion:

• Include/skip recursion: choose the current candidate or skip to the next one.
• Loop-based recursion: loop over all candidates from start onward.

Both can work. I prefer the loop here because the allowed range is visible in one place, and the sorted break becomes obvious.

Build the Search State and Transition

Each recursive call needs three pieces of state:

The recursive function explores every candidate from start onward.

For a candidate at index i:

1. Append candidates[i] to path.
2. Subtract it from remaining.
3. Recurse from index i, not i + 1.
4. Remove the candidate from path before trying the next sibling branch.

That third step is the critical unlimited-reuse detail.

recurse(i, remaining - candidates[i])

means the next call may choose the same candidate again.

recurse(i + 1, remaining - candidates[i])

would mean the candidate is now exhausted. That is the rule for a single-use variant, not this problem.

For [2, 3, 6, 7] and target 7, one branch develops like this:

path = []
remaining = 7

choose 2
path = [2], remaining = 5

choose 2 again
path = [2, 2], remaining = 3

choose 2
remaining = 1

At this point, 2 is too large for the remaining target, so that branch stops. Backtrack to [2, 2], then try 3:

path = [2, 2, 3], remaining = 0

Record a copy of the path. Later, the search reaches the separate [7] branch.

The search is a controlled walk through frequency patterns. It is not throwing numbers into a bag and hoping the sum works out.

Prune with a Remaining-Target Invariant

The implementation becomes easier to trust once the recursive invariant is explicit.

At every call, path is in nondecreasing candidate order, sum(path) + remaining equals the original target, and every valid completion using candidates from start onward is still reachable.

Each rule preserves part of that statement:

• Appending a candidate at or after start preserves nondecreasing order.
• Subtracting the candidate preserves the target equation.
• Recursing with the same index preserves reuse.
• Recursing with a larger index prevents earlier candidates from reappearing.

There are two important stopping conditions.

Completion

When remaining == 0, the current path is valid:

result.append(path.copy())
return

The copy matters. path is mutable and will later be changed by pop(). Storing the list itself would make previously recorded answers change as the search continues.

Because all candidates are positive, extending a complete path would only increase its sum. There is no reason to explore beyond zero.

Overshoot

After sorting, if candidates[i] > remaining, stop the loop.

Every later candidate is at least as large as candidates[i], so none of them can fit either. Positivity makes overshoot permanent: adding more values can never bring the sum back down.

This is why sorting is more than cosmetic. It turns an invalid candidate into a proof that every later candidate is invalid too.

The two controls have different responsibilities:

• start prevents duplicate orderings.
• remaining and the sorted break prune impossible sums.

Do not confuse them. Removing the break makes the code slower. Removing start changes the output.

Python Implementation: Append, Recurse, Pop

from typing import List


def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
    candidates = sorted(candidates)
    result: List[List[int]] = []
    path: List[int] = []

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            result.append(path.copy())
            return

        for i in range(start, len(candidates)):
            candidate = candidates[i]

            if candidate > remaining:
                break

            path.append(candidate)

            # Recurse with i, not i + 1:
            # the same candidate may be used again.
            backtrack(i, remaining - candidate)

            # Restore path before exploring the next sibling.
            path.pop()

    backtrack(0, target)
    return result

The names mirror the proof:

• start enforces canonical order.
• remaining is the pruning budget.
• path is the current partial combination.
• result stores completed combinations.

The control flow is deliberately plain:

append
recurse
pop

That sequence is the backtracking mechanism. append moves down one branch. recurse explores the consequences. pop restores the state so the next branch starts clean.

Using sorted(candidates) creates a new list rather than changing the caller's list in place. The algorithm needs sorted values for pruning, but it does not need to impose that side effect on its input.

Dry-Run the Failure Modes

The happy path is not enough. Backtracking bugs usually appear when a branch reuses a value, overshoots, or leaves mutable state behind.

Repeated use: [2, 3, 5], target 8

The algorithm can choose 2 repeatedly because recursion stays at the same index:

[2]       remaining 6
[2, 2]    remaining 4
[2, 2, 2] remaining 2
[2, 2, 2, 2] remaining 0

That records:

[2, 2, 2, 2]

From [2], the search can also move to 3:

[2, 3]     remaining 3
[2, 3, 3]  remaining 0

And from the top-level 3 branch:

[3, 5] remaining 0

The results are:

[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Notice that [3, 2, 3] never appears. Once the branch moves from index 2 to index 3, it cannot return to the earlier 2.

Immediate overshoot: [2], target 1

The first candidate is already too large:

candidate = 2
remaining = 1

The sorted break runs before 2 is appended. No recursive branch is created, and the result is:

[]

This is a small case, but it tests whether the pruning condition is placed correctly.

Restoring sibling state

Suppose the search reaches:

path = [2, 2]

It tries 3, records [2, 2, 3], returns, and executes:

path.pop()

The path is back to:

[2, 2]

Then the function returns again and pops the second 2, restoring:

[2]

Now it can try the next candidate from the [2] branch. Without the pop, the next sibling would inherit values from a completed or failed branch. That produces malformed combinations and is one of the most common backtracking mistakes.

The rule is simple: every append must have exactly one matching pop after its recursive call.

Prove It, Bound It, and Check the Edges

Correctness

The algorithm records only valid combinations. It appends a path only when remaining == 0. Since remaining begins at target and decreases by every chosen value, the path sum is exactly the target.

It also reaches every valid combination. Any combination can be written in nondecreasing order. Starting at index 0, the loop can choose its first value; each recursive call can choose the same value again or move to a later value. Therefore, the ordered representation of every valid combination remains reachable.

Finally, it records no combination twice. The start index forces every path to be nondecreasing. A frequency pattern has only one nondecreasing representation, so different permutations cannot create duplicate results.

Complexity

Sorting costs:

O(n log n)

where n is the number of candidates.

The backtracking portion is output-sensitive. It may explore many partial paths before finding or rejecting combinations, so the worst-case runtime is exponential in the input magnitude and target. There is no useful universal polynomial bound: the algorithm is enumerating combinations, and the number of combinations itself can grow rapidly.

The exact work depends on:

• the target,
• the smallest candidate,
• how many candidates fit each remaining value,
• and how many valid or nearly valid paths exist.

Auxiliary space includes the recursion stack and the mutable path. Since every candidate is positive, a path cannot contain more than roughly target / min(candidates) values. The stored output is separate: every successful path is copied into result, and that output space may dominate memory.

Interview edge checks

Before submitting, verify these mechanics:

• The candidates are sorted.
• The base case checks remaining == 0.
• A successful path uses path.copy().
• The loop begins at start, never at 0.
• Reuse recurses with i, not i + 1.
• The path is popped after recursion.
• The loop breaks when a sorted candidate exceeds remaining.
• A target smaller than every candidate returns an empty list.
• A candidate equal to the target produces a one-element combination.
• The smallest candidate can be used repeatedly.
• No reordered duplicate can appear.

The reusable recognition rule is compact:

When values are positive, reuse is allowed, order does not matter, and partial sums only grow, choose one canonical order, carry the remaining budget, recurse from the same index for reuse, and prune when the budget cannot be met.

Derive the state first. Preserve its invariant. Undo every mutation. That is the backtracking skill this problem is really testing.