Problem Statement

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.

Additional information

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

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.
• These are the only two combinations.

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: []

Solution

Brute Force (Naive DFS with Post-Filtering)

Intuition

A naive way to approach this is to generate absolutely every possible sequence of numbers that sums up to the target, without caring about order. At each step, we could try adding any number from the candidates array to our current combination until we hit the target.

However, this creates a massive problem: permutations. If we just blindly pick numbers, we will generate [2, 2, 3], [2, 3, 2], and [3, 2, 2] as separate valid answers. To fix this in a brute-force way, we would have to sort every valid combination we find, convert it to a tuple, and store it in a set to filter out the duplicates.

Algorithm

1. Initialize an empty set called res_set to hold our unique combinations.
2. Create a recursive function dfs(current_comb, current_sum).
3. If current_sum == target, sort current_comb, convert it to a tuple, and add it to res_set. Then return.
4. If current_sum > target, simply return (we overshot the target).
5. Loop through every num in candidates.
6. For each num, append it to current_comb, call dfs, and then backtrack by popping it off.
7. After the recursion finishes, convert the set of tuples back to a list of lists and return.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    res_set = set()
    
    def dfs(current_comb, current_sum):
        if current_sum == target:
            # Sort and convert to tuple to ensure uniqueness in the set
            res_set.add(tuple(sorted(current_comb)))
            return
        if current_sum > target:
            return
            
        # Naively try every candidate at every step
        for num in candidates:
            current_comb.append(num)
            dfs(current_comb, current_sum + num)
            current_comb.pop()
            
    dfs([], 0)
    return [list(comb) for comb in res_set]

Time & Space Complexity

• Time complexity: O(N^(T/M) * (T/M) log(T/M))

• Reason: N is the number of candidates, T is the target, and M is the minimum value in candidates. The maximum depth of the recursion tree is T/M. At each node, we branch out N times. We also spend time sorting valid combinations at the leaf nodes.

• Space complexity: O(T/M)

• Reason: The recursion stack and the current_comb array take space proportional to the maximum length of a combination, which is T/M.

Recursive Backtracking (Index Tracking) - Optimal

Intuition

We can completely avoid generating duplicate permutations by enforcing a simple rule: Once we decide to move on from a candidate, we can never look back at it.

We can achieve this by passing an index pointer into our DFS function. At any given point, our two choices are:

1. Include the candidate at the current index. Because we can reuse numbers, we do not increment the index for the next recursive call.
2. Exclude the candidate at the current index and move on to the next one. We increment the index and cannot use the previous numbers anymore.

By strictly moving forward through the candidates array, it becomes impossible to generate both [2, 3] and [3, 2].

Algorithm

1. Initialize an empty list res for the final valid combinations.
2. Define a recursive helper dfs(i, current_comb, total) where i is the current index in candidates.
3. Base Cases:

• If total == target, we found a valid combination! Append a .copy() of current_comb to res and return.
• If i >= len(candidates) or total > target, we hit a dead end. Return immediately to prune this branch.

4. Decision 1: Include the current candidate.

• Append candidates[i] to current_comb.
• Recursively call dfs(i, current_comb, total + candidates[i]). (Notice i stays the same so we can reuse it).

5. Decision 2: Exclude the current candidate.

• Backtrack by popping the last added element: current_comb.pop().
• Recursively call dfs(i + 1, current_comb, total). (Increment i to move to the next candidate).

6. Call dfs(0, [], 0) and return res.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    res = []
    
    def dfs(i, current_comb, total):
        if total == target:
            res.append(current_comb.copy())
            return
        if i >= len(candidates) or total > target:
            return
            
        # Decision 1: Include candidates[i]
        current_comb.append(candidates[i])
        dfs(i, current_comb, total + candidates[i])
        
        # Decision 2: Exclude candidates[i] and move to the next
        current_comb.pop()
        dfs(i + 1, current_comb, total)
        
    dfs(0, [], 0)
    return res

Time & Space Complexity

• Time complexity: O(2^(T/M))

• Reason: In the worst case, the algorithm explores a binary decision tree (include or exclude). The height of this tree is bounded by T/M (where T is the target sum and M is the smallest element in candidates). Therefore, the number of nodes is roughly 2^(T/M).

• Space complexity: O(T/M)

• Reason: Excluding the output array, the auxiliary space is strictly bounded by the maximum depth of the recursion stack, which occurs when we repeatedly pick the smallest element until exceeding the target.