• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• 1 <= target <= 500
• All candidates are distinct positive integers
• Each candidate may be reused without limit

Two things separate this from Combinations, and taking them one at a time makes the solution fall out.

First, candidates may be reused. Second, the answer is not defined by a length but by a running total, which introduces a genuine new capability: the search can now tell it has failed before reaching any leaf.

Recall how Combinations avoided duplicates: after choosing the number at index i, the next choice came from index i+1 onward. Paths were strictly increasing, so each set had exactly one representation and reorderings could not be built.

Here the same duplicate problem exists — [2,2,3] and [2,3,2] and [3,2,2] describe one answer — so the same idea applies, with one relaxation. Paths must be non-decreasing rather than strictly increasing, because repeating a value is now legal while going backwards still is not.

In code that is the difference between passing i + 1 and passing i:

Passing i keeps index i in the choice space while permanently excluding everything before it, which is precisely "may repeat, may not go back". One character encodes the entire difference between two problems, and being able to say why is worth more than memorising either.

Now the more interesting change. Track how much of the target remains, subtracting each chosen candidate.

Three situations arise at any node, and only one continues:

That second case is the new capability. In Subsets, Combinations and Permutations, every partial path could still become a valid answer, so the search never abandoned anything — it simply ran to the leaves. Here a branch can be proven hopeless partway down and cut immediately, along with everything beneath it.

def combination_sum(candidates, target):
    result = []
    path = []

    def build(start, remain):
        if remain == 0:
            result.append(list(path))     # exact hit: snapshot a copy
            return
        if remain < 0:
            return                        # PRUNE: overshot, unrecoverable

        for i in range(start, len(candidates)):
            path.append(candidates[i])            # CHOOSE
            build(i, remain - candidates[i])      # EXPLORE — 'i', not 'i + 1'
            path.pop()                            # UN-CHOOSE

    build(0, target)
    return result

The version above discovers an overshoot only after recursing into it — the child call computes a negative remainder and returns immediately. That call was avoidable.

Sort the candidates first. Then, once a candidate exceeds the remainder, every subsequent candidate does too, so the loop can break rather than skip:

def combination_sum(candidates, target):
    candidates.sort()                     # enables the break below
    result, path = [], []

    def build(start, remain):
        if remain == 0:
            result.append(list(path))
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break                     # sorted: every later candidate is worse too
            path.append(candidates[i])
            build(i, remain - candidates[i])
            path.pop()

    build(0, target)
    return result

The remain < 0 base case is now unreachable and can be dropped, since no overshooting call is ever made. The complexity bound is unchanged — it is dominated by the answers actually produced — but the constant improves substantially, and on adversarial inputs it is the difference between passing and timing out.

Sorted already. Following the branch starting with 2:

Result [[2,2,3],[7]]. The two moments worth noticing are the break at remainder 1, which skipped three candidates without testing them, and the start index at build(1, 2), which made the duplicate [2,3,2] structurally impossible.

The section's skeleton is unchanged; only the slots differ:

Two independent decisions determine which you are in. Does order matter? If not, use a start index. May items repeat? If so, pass i; if not, i + 1.

The genuinely new idea here is pruning on the objective. Earlier problems pruned structurally, if at all — the start index prevented duplicates from being built. This one prunes on a value computed from the path, abandoning branches that have already failed. N-Queens and Sudoku take that much further, testing constraints at every single placement.

Recognition signals: make change with given coins, reach a target sum, fill a knapsack exactly, all ways to score n points. A caveat worth stating: if the question asks only how many ways, or only the minimum number of items, dynamic programming is far better — backtracking is for when you must produce the combinations themselves.

Train the reflex: when the path carries a running value with a monotone relationship to the goal, check it at every node. A branch you can prove hopeless is a whole subtree you never have to walk.