Combination Sum

Intuition

Sorting lets us stop scanning as soon as a candidate is larger than what remains, because everything after it is even larger. To avoid producing the same multiset in different orders, each recursive call only considers candidates from the current index onward. Passing the same index into the next call permits reuse of a value, while advancing the index in the loop guarantees we never revisit an earlier smaller value and create a duplicate ordering.

Algorithm walkthrough

1. 1Sort candidates in ascending order so we can prune early.
2. 2Track the remaining amount and the path of chosen numbers.
3. 3When the remaining amount hits zero, save a copy of the current path.
4. 4Loop from the current start index; if a candidate exceeds the remaining amount, break because later ones are bigger.
5. 5Choose a candidate, recurse with the same index to allow reuse, then remove it to backtrack.

Implementation

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

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

        backtrack(0, target, [])
        return result