Combination Sum

Problem

Given an array of distinct positive integers and a target, return every unique combination of numbers that sums to the target. The same number can be used any number of times, and combinations that differ only in order count as the same.

Approach

Use backtracking. Build a combination one number at a time and track how much of the target is left.

Pass a start index into each call and only pick candidates from that index onward. Staying on the same index allows reuse, and never going back stops the same combination from appearing in a different order.

Sort the candidates first so the loop can stop as soon as a candidate is larger than what remains.

Solution

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        result = []
        path = []

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

        backtrack(0, target)
        return result

Complexity

• Time: Exponential in the worst case, roughly O(n^(t/m)) where t is the target and m is the smallest candidate.
• Space: O(t/m) for the recursion depth and the current path, excluding the output.

Edge cases

• A target smaller than every candidate returns an empty list.
• A candidate equal to the target is a valid one-number combination.
• Small candidates such as 1 create the deepest recursion.