Combination Sum

Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

Solution

Approach: Backtracking with Reuse

The key insight is to use backtracking where we can reuse the same element multiple times. To avoid duplicates, we always progress forward in the candidates array.

Implementation

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

        def backtrack(start, path, remaining):
            if remaining == 0:
                result.append(path[:])
                return

            if remaining < 0:
                return

            for i in range(start, len(candidates)):
                path.append(candidates[i])
                # Can reuse same element, so pass i (not i+1)
                backtrack(i, path, remaining - candidates[i])
                path.pop()

        backtrack(0, [], target)
        return result

Optimized (Sort + Prune):

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

        def backtrack(start, path, remaining):
            if remaining == 0:
                result.append(path[:])
                return

            for i in range(start, len(candidates)):
                # Prune: if current candidate > remaining, all after will too
                if candidates[i] > remaining:
                    break

                path.append(candidates[i])
                backtrack(i, path, remaining - candidates[i])
                path.pop()

        backtrack(0, [], target)
        return result

Complexity Analysis

Time Complexity: O(n^(t/m)), where n is the number of candidates, t is target, and m is minimal candidate value. In the worst case, we explore all possible combinations.
Space Complexity: O(t/m) for recursion depth.

Key Insights

Unlimited Reuse: We can use the same element multiple times, so we pass i (current index) not i+1 in recursion.
Avoid Duplicates: By always moving forward (or staying at same index), we avoid duplicate combinations like [2,3] and [3,2].
Early Termination: When remaining becomes negative, we can stop exploring that branch.
Sorting Optimization: Sorting candidates allows us to break early when a candidate exceeds remaining sum.
Decision Tree: At each step, we decide how many times to use current candidate (0, 1, 2, … times) before moving to the next.