Problem Statement

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Additional information

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

Example 1:

Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8

Output: 
[
  [1, 1, 6],
  [1, 2, 5],
  [1, 7],
  [2, 6]
]

Example 2:

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

Output: 
[
  [1, 2, 2],
  [5]
]

Brute Force (DFS with Sets for Deduplication)

Intuition

A naive way to solve this is to completely ignore the fact that there are duplicates in the input array. We can just run a standard Depth-First Search (DFS) to find every single combination of elements that sums to our target. Since we can only use each element once, we just move our index forward by 1 in every recursive step.

Because the input has duplicate numbers (like multiple 1s or 2s), this approach will inevitably generate duplicate valid combinations. To fix this, we can sort every valid combination we find, convert it to a tuple, and store it in a set. The set will automatically filter out all the duplicates.

Algorithm

1. Initialize a set called res_set to hold our unique combinations.
2. Define a recursive function dfs(i, current_comb, current_sum) where i is our current index in candidates.
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 or i >= len(candidates), return immediately (dead end).
5. Decision 1: Include the current candidate. Append candidates[i] to the combination and recurse with dfs(i + 1, current_comb, current_sum + candidates[i]).
6. Decision 2: Exclude the current candidate. Pop the last added element and recurse with dfs(i + 1, current_comb, current_sum).
7. Once the recursion finishes, convert the set of tuples back to a list of lists and return.

def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    res_set = set()
    
    def dfs(i, current_comb, current_sum):
        if current_sum == target:
            # Sort and tuple to ensure uniqueness in the set
            res_set.add(tuple(sorted(current_comb)))
            return
        if current_sum > target or i >= len(candidates):
            return
            
        # Include candidates[i]
        current_comb.append(candidates[i])
        dfs(i + 1, current_comb, current_sum + candidates[i])
        
        # Exclude candidates[i]
        current_comb.pop()
        dfs(i + 1, current_comb, current_sum)
        
    dfs(0, [], 0)
    return [list(comb) for comb in res_set]

Time & Space Complexity

• Time complexity: O(2^N * N log N)

• Reason: In the worst case, we explore a binary tree of height N (where N is the number of candidates), yielding up to 2^N combinations. For valid combinations, we spend O(N log N) time sorting them before adding them to the set.

• Space complexity: O(2^N * N)

• Reason: The res_set might store an exponential number of tuples, each taking up to O(N) space.

Recursive Backtracking with Pruning - Optimal

Intuition

We can completely avoid generating duplicates in the first place, saving a massive amount of time and memory. The trick is to sort the candidates array first. This groups all duplicate numbers together.

Instead of a simple "include/exclude" binary choice, we use a for loop inside our DFS to try picking every available number for the current position in our combination.

If we are iterating through our choices for a specific slot in the combination, and we see that the current number is exactly the same as the previous number we just tried, we continue and skip it! Because the array is sorted, trying it again would just generate the exact same branch of combinations we just finished exploring.

Algorithm

1. Sort the candidates array.
2. Initialize an empty list res for the final unique combinations.
3. Create a recursive helper dfs(start_index, current_comb, current_sum).
4. Base Case: If current_sum == target, append a .copy() of current_comb to res and return.
5. Loop & Prune: Start a for loop with i from start_index to the end of the array:

• Prune Overshoot: If current_sum + candidates[i] > target, we can break out of the loop entirely! Because the array is sorted, every subsequent number will also be too big.
• Prune Duplicates: If i > start_index and candidates[i] == candidates[i - 1], continue. This ensures we don't start a duplicate branch at the exact same depth.
• Recurse: Append candidates[i], call dfs(i + 1, current_comb, current_sum + candidates[i]), and then .pop() it to backtrack.

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

def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    res = []
    
    def dfs(start_index, current_comb, current_sum):
        if current_sum == target:
            res.append(current_comb.copy())
            return
            
        for i in range(start_index, len(candidates)):
            # Prune: if this number exceeds the target, all remaining numbers will too
            if current_sum + candidates[i] > target:
                break
                
            # Prune: skip duplicates at the same tree depth
            if i > start_index and candidates[i] == candidates[i - 1]:
                continue
                
            current_comb.append(candidates[i])
            # Pass i + 1 because each number can only be used once
            dfs(i + 1, current_comb, current_sum + candidates[i])
            current_comb.pop()
            
    dfs(0, [], 0)
    return res

Time & Space Complexity

• Time complexity: O(2^N)

• Reason: Sorting takes O(N log N). In the absolute worst case (where every combination is valid and unique), there are 2^N combinations. However, the aggressive pruning (skipping duplicates and breaking early on overshoots) makes the average runtime drastically faster than the theoretical upper bound.

• Space complexity: O(N)

• Reason: Excluding the output array, the auxiliary space is strictly bounded by the maximum depth of the recursion stack, which is exactly the length of the candidates array, O(N).