Combination Sum

Signal

"Combinations summing to a target, with unlimited reuse of each candidate" backtracks like subsets, but with one twist: because a candidate can be reused, the recursive call can stay at the same index instead of always advancing.

Approach

Backtrack with a running remainder and a start index. If the remainder hits zero, record the path. Otherwise, try each candidate from start onward: include it, recurse with the same index (it can be reused), then remove it. Prune the moment a candidate exceeds the remaining amount — nothing under it can still reach the target from a sorted list.

Skeleton

def backtrack(start, remaining, path):
    if remaining == 0: results.append(copy of path); return
    for i in range(start, len(candidates)):
        if candidates[i] > remaining: continue
        path.append(candidates[i])
        backtrack(i, remaining - candidates[i], path)
        path.pop()

Solution

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    results: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            results.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return results

Complexity

Exponential in the target size divided by the smallest candidate — roughly bounded by the number of ways to sum to target, which the remaining < 0 prune keeps well below a naive brute force. Space is O(target / min(candidates)) for recursion depth, plus O(n) per stored combination.

Pitfalls

• Advancing to i + 1 instead of staying at i on the recursive call — that silently forbids reuse, turning this into "combination sum without repetition", a different problem.
• Starting the loop at 0 instead of start on every call — that records the same combination multiple times in different element orders (e.g. [2, 3] and [3, 2] both saved).
• Not pruning on candidates[i] > remaining — still correct without it, but it explores far more dead branches, especially with large candidates.