Combination Sum

You are given an array of distinct integers nums and a target integer target. Your task is to return a list of all unique combinations of nums where the chosen numbers sum to target.

The same number may be chosen from nums an unlimited number of times. Two combinations are the same if the frequency of each of the chosen numbers is the same, otherwise they are different.

You may return the combinations in any order and the order of the numbers in each combination can be in any order.

2 + 2 + 5 = 9. We use 2 twice, and 5 once.
9 = 9. We use 9 once.

Approach

Use backtracking with a running path and remaining target. At each step, choose a candidate starting from the current index (so we can reuse it) and recurse with the reduced target. Sort candidates to allow early stopping when the remaining target is negative.

Why It Works

Every valid combination can be represented as a non-decreasing sequence of candidates. The backtracking explores exactly these sequences, adding a path to the result only when the remaining target reaches zero. Sorting and index control ensure we don't miss any combination or generate duplicates.

Complexity

• Time: Exponential in the number of combinations
• Space: O(target) recursion depth

Reference Implementation (Python)

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

        def dfs(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])
                dfs(i, remaining - candidates[i], path)
                path.pop()

        dfs(0, target, [])
        return result