#39MediumBacktracking

Combination Sum

The tell: All combinations reaching a target, with unlimited reuse of each candidate.

How you get there

1Recurse with the remaining target rather than the running sum.
2Passing i rather than i + 1 permits reusing the same candidate.
3Prune as soon as the remainder goes negative.

Solution

Python

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

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            out.append(path[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])   # i, not i + 1: reuse allowed
            path.pop()

    backtrack(0, target)
    return out

Time: O(n^(target/min))
Space: O(target/min)

What goes wrong

Recursing from 0 instead of i produces the same combination in every order.

Test yourself on DSA Next: Permutations →