Combination Sum

Unlimited reuse makes the search tree deep, but positive values give you a hard brake: the remaining sum always falls after a choice.

Let n be the number of candidates, m the smallest candidate, d = target // m the maximum answer length, and k the number of returned combinations.

Enumerate multiplicities

Multiplicity means the number of copies you take. For each candidate, try every legal multiplicity before moving to the next candidate. Because candidates are processed in sorted order, every completed path is already non-decreasing and represents one unique combination.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    values = sorted(candidates)
    answer: list[list[int]] = []
    path: list[int] = []
 
    def search(index: int, remaining: int) -> None:
        if index == len(values):
            if remaining == 0:
                answer.append(path.copy())
            return
 
        value = values[index]
        max_count = remaining // value
 
        for count in range(max_count + 1):
            path.extend([value] * count)
            search(index + 1, remaining - count * value)
            for _ in range(count):
                path.pop()
 
    search(0, target)
    return answer

This baseline tests a full grid of candidate counts, including many partial assignments that can't finish the remaining sum.

Time O((d + 1)^n · d). Space O(n + d + k · d) including recursion, the current combination, and the returned output.

Reuse-aware backtracking

Backtracking chooses a candidate, explores that choice, then un-chooses it. The partial sums form a solution-space tree, a tree whose nodes are growing combinations. Sorting lets the search prune, or stop exploring, every later choice as soon as one value is too large. This is the choose/explore/un-choose backtracking pattern with reuse kept on the explore step.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    values = sorted(candidates)
    answer: list[list[int]] = []
    path: list[int] = []
 
    def search(start: int, remaining: int) -> None:
        if remaining == 0:
            answer.append(path.copy())
            return
 
        for i in range(start, len(values)):
            value = values[i]
            if value > remaining:
                break
 
            path.append(value)          # choose
            search(i, remaining - value)  # explore; i allows reuse
            path.pop()                  # un-choose, then the loop advances
 
    search(0, target)
    return answer

Passing i keeps the chosen value available. Passing start forward and never backward means [2, 2, 3] is generated, while reordered copies such as [3, 2, 2] never enter the tree. Positive candidates guarantee the recursion reaches either zero or a dead end.

Time O(n^d · d). Space O(d + k · d) in a loose worst-case bound, including the returned output. In practice, sorted-order pruning removes most of that theoretical tree.