Combination Sum II

You are given an array of integers candidates, which may contain duplicates, and a target integer. Your task is to return a list of all unique combinations of candidates where the chosen numbers sum to target.

Each element from candidates may be chosen at most once within a combination. The solution set must not contain duplicate combinations.

Examples

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Backtracking - Exploring choices by including/excluding elements and undoing decisions when needed.
• Sorting - Arranging elements to group duplicates together for efficient skip logic.
• Handling Duplicates - Skipping repeated elements at the same recursion level to avoid duplicate combinations.

1. Brute Force (Using Set)

Intuition

The brute-force approach tries every possible subset of the candidate numbers. We sort the array so duplicate combinations appear in the same order. At each index, we have two choices: Include the current number, or Skip the current number. Whenever a subset’s sum equals the target, we store it.

To avoid duplicate combinations, we store each result as a tuple in a Set. This method is easy to understand but slow because it explores all subsets, even invalid or duplicate ones.

Sort the array to keep combinations in consistent order.
Use a recursive function dfs(i, currentList, total):
  If total == target, add the tuple version of currentList to a set
  If total > target or i == len(candidates), stop exploring
  
  At each index i:
    // Include the current number:
    Add it to currentList, recurse with i + 1, then remove it
    
    // Exclude the current number:
    Recurse with i + 1
    
After recursion finishes, convert all unique tuples in the set into lists and return them.

2. Backtracking (Optimal Deduplication)

Intuition

We need all unique combinations where each number can be used at most once, and duplicates in the input should not create duplicate combinations. To handle duplicates safely, we:

• Sort the array: This groups equal numbers together, which helps us skip duplicates easily.
• Skip duplicates at the same level: If candidates[i] == candidates[i - 1] and we are still in the same level of recursion (i > idx), we skip that number.
• Stop early: If curSum + candidates[i] > target, we break early because the list is sorted.

This approach explores each number only once per combination path and guarantees no repeated results.

Sort the candidates.
Define a DFS function dfs(idx, path, curSum):
  If curSum == target:
    Add a copy of path to the result
    Return
    
  Loop i from idx to len(candidates) - 1:
    If i > idx and candidates[i] == candidates[i - 1]:
      Continue (duplicate control)
      
    If curSum + candidates[i] > target:
      Break (pruning)
      
    Include the number and recurse with dfs(i + 1, path, curSum + candidates[i])
    Backtrack by removing the last number

Call dfs(0, [], 0) and return the result.

Time Complexity: O(2^N) in the worst case (though practically much faster due to pruning and duplicate skipping).

Space Complexity: O(N) for the recursion stack.

Common Pitfalls

Generating Duplicate Combinations

The input contains duplicates, and each element can only be used once. Without proper duplicate handling, [1,1,2] with target 3 might produce [1,2] twice. Always sort first and skip consecutive duplicates at the same recursion level.

# Wrong: generates duplicates for i in range(idx, len(candidates)): dfs(i + 1, ...) # Correct: skip duplicates at same level for i in range(idx, len(candidates)): if i > idx and candidates[i] == candidates[i - 1]: continue dfs(i + 1, ...)

Reusing Elements (Using i Instead of i + 1)

Unlike Combination Sum I where elements can be reused, this problem requires each element to be used at most once. Recursing with the same index allows reuse.

# Wrong: allows reusing same element dfs(i, cur, total + candidates[i]) # Correct: move to next element dfs(i + 1, cur, total + candidates[i])

Forgetting to Sort Before Skipping Duplicates

The duplicate-skipping logic candidates[i] == candidates[i-1] only works on a sorted array. Without sorting, duplicates won't be adjacent and the skip logic fails silently, producing duplicate combinations.