Combination Sum II

LeetCode 40: Combination Sum II Solution & Explanation

Problem Overview

TL;DR: The optimal solution involves sorting the input array to group duplicates, then performing a backtracking depth-first search that skips adjacent identical elements at the same recursion depth to ensure unique combinations.

LeetCode 40, Combination Sum II, asks us to find all unique combinations of numbers from a given candidate array that sum up to a specific target value. Unlike the standard Combination Sum problem, each number in the input array may only be used once per combination. Additionally, the input array may contain duplicate numbers, but the final solution set must not contain duplicate combinations.

This is a popular interview question because it tests the ability to handle combinatorial constraints and effectively prune a recursion tree to avoid redundancy.

Brute Force Approach for Combination Sum II

The naive approach attempts to generate every possible subset of the candidates array, calculates the sum of each subset, and checks if it equals the target. Since the problem requires unique combinations, a brute force solution would also need a mechanism to filter out duplicates after generation (e.g., by storing results in a Set).

Pseudo-code for Naive Approach:

function getAllSubsets(index, currentPath, currentSum):
    if currentSum == target:
        sort currentPath
        addToSet(currentPath) // Set handles uniqueness
        return

    if index >= candidates.length or currentSum > target:
        return

    // Include current element
    getAllSubsets(index + 1, currentPath + candidates[index], currentSum + candidates[index])

    // Exclude current element
    getAllSubsets(index + 1, currentPath, currentSum)

Why this fails:

1. Inefficiency: The time complexity approaches $O(2^N \cdot N)$ because it generates the power set. With $N=100$, $2^{100}$ is computationally impossible.
2. Redundant Processing: It explores paths that are guaranteed to fail (sum > target) or guaranteed to be duplicates without pruning them early.
3. Post-processing cost: Relying on a Set to filter duplicates after generating them is significantly slower than preventing duplicates during generation.

Algorithm Strategy: Backtracking Patterns

The strategy relies on a Depth-First Search (DFS) traversal of the decision tree.

1. Sort the Input: Sort candidates in ascending order. This puts duplicates adjacent to each other and allows for early termination if the current sum exceeds the target.
2. State Management: Maintain a current_combination list and a remaining_target value.
3. Recursive Function: Define a function backtrack(start_index, target):
   • Goal: If target == 0, add a copy of current_combination to the results.
   • Constraint: Loop through the array from start_index to the end.
   • Duplicate Pruning: Inside the loop, check if i > start_index and candidates[i] == candidates[i-1]. If true, continue to the next iteration.
   • Value Pruning: If candidates[i] > target, break the loop immediately (since the array is sorted, all subsequent numbers will also be too large).
   • Forward Step: Add candidates[i] to current_combination.
   • Recurse: Call backtrack(i + 1, target - candidates[i]). Note that we pass i + 1 because elements cannot be reused.
   • Backtrack: Remove the last added element from current_combination to restore the state for the next iteration.

Execution Flow

Let's trace candidates = [10, 1, 2, 7, 6, 1, 5], target = 8.

1. Sort: [1, 1, 2, 5, 6, 7, 10].
2. Start Backtrack: index = 0, target = 8.
3. Loop i = 0 (val = 1):
   • Add 1. Path: [1]. Remaining: 7.
   • Recurse (index 1):
     • Loop j = 1 (val = 1):
       • Add 1. Path: [1, 1]. Remaining: 6.
       • Recurse (index 2):
         • ... eventually finds 6. Path [1, 1, 6] added.
       • Backtrack. Path: [1].
     • Loop j = 2 (val = 2):
       • Add 2. Path: [1, 2]. Remaining: 5.
       • ... eventually finds 5. Path [1, 2, 5] added.
       • Backtrack. Path: [1].
     • ...
   • Backtrack. Path: [].
4. Loop i = 1 (val = 1):
   • Check: i > start_index (1 > 0) AND candidates[1] == candidates[0] (1 == 1).
   • SKIP. We already explored all combinations starting with a 1 in the previous iteration.
5. Loop i = 2 (val = 2):
   • Add 2. Path: [2]. Remaining: 6.
   • Recurse (index 3):
     • ... eventually finds 6. Path [2, 6] added.
   • Backtrack. Path: [].
6. Continue until all options explored.

Proof of Correctness

The correctness relies on the sorted order and the loop condition.

1. Validity: The recursion only adds a combination if target == 0.
2. Constraint Compliance: We pass i + 1 to the recursive call, ensuring the index i is not reused, satisfying the "each number used once" constraint.
3. Uniqueness: The condition if (i > start && candidates[i] == candidates[i-1]) continue mathematically guarantees that for any specific position in a combination, a specific value is only chosen once. Since the list is sorted, skipping duplicates here prevents generating permutations of the same multiset.

Pattern Reuse Notes

The logic used in LeetCode 40 Solution is highly transferable to other backtracking problems:

• LeetCode 39: Combination Sum: The logic is nearly identical, except we pass i instead of i+1 to the recursive call to allow element reuse, and we don't need the duplicate skipping logic if inputs are distinct.
• LeetCode 90: Subsets II: Uses the exact same i > start && nums[i] == nums[i-1] logic to generate unique subsets from a collection with duplicates.

Reference Implementation

C++ Solution for LeetCode 40

1class Solution {
2public:
3    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
4        vector<vector<int>> result;
5        vector<int> current;
6        // Sorting is essential for duplicate handling and early termination
7        sort(candidates.begin(), candidates.end());
8        
9        backtrack(candidates, target, 0, current, result);
10        return result;
11    }
12
13private:
14    void backtrack(const vector<int>& candidates, int target, int start, 
15                   vector<int>& current, vector<vector<int>>& result) {
16        if (target == 0) {
17            result.push_back(current);
18            return;
19        }
20
21        for (int i = start; i < candidates.size(); ++i) {
22            // Early termination: if current number exceeds target, 
23            // subsequent numbers will too (since sorted)
24            if (candidates[i] > target) break;
25
26            // Skip duplicates: if this is not the first number in this 
27            // recursive step and it's the same as the previous one, skip it.
28            if (i > start && candidates[i] == candidates[i - 1]) continue;
29
30            current.push_back(candidates[i]);
31            // Recurse with i + 1 because elements cannot be reused
32            backtrack(candidates, target - candidates[i], i + 1, current, result);
33            current.pop_back(); // Backtrack
34        }
35    }
36};

Java Solution for LeetCode 40

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
7        List<List<Integer>> result = new ArrayList<>();
8        Arrays.sort(candidates); // Sort to handle duplicates and pruning
9        backtrack(result, new ArrayList<>(), candidates, target, 0);
10        return result;
11    }
12
13    private void backtrack(List<List<Integer>> result, List<Integer> current, 
14                           int[] candidates, int remaining, int start) {
15        if (remaining == 0) {
16            result.add(new ArrayList<>(current)); // Deep copy
17            return;
18        }
19
20        for (int i = start; i < candidates.length; i++) {
21            // Optimization: Stop if candidate exceeds remaining target
22            if (candidates[i] > remaining) break;
23
24            // Skip duplicates at the current depth
25            if (i > start && candidates[i] == candidates[i - 1]) continue;
26
27            current.add(candidates[i]);
28            // Move to i + 1 to avoid reusing the same element
29            backtrack(result, current, candidates, remaining - candidates[i], i + 1);
30            current.remove(current.size() - 1); // Backtrack
31        }
32    }
33}

Python Solution for LeetCode 40

1class Solution:
2    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
3        result = []
4        candidates.sort() # Essential for duplicate logic
5        
6        def backtrack(start_index, current_path, remaining_target):
7            if remaining_target == 0:
8                result.append(list(current_path)) # Append copy
9                return
10            
11            for i in range(start_index, len(candidates)):
12                candidate = candidates[i]
13                
14                # Optimization: Stop if candidate exceeds target
15                if candidate > remaining_target:
16                    break
17                
18                # Skip duplicates: prevent processing same number at same depth
19                if i > start_index and candidates[i] == candidates[i-1]:
20                    continue
21                
22                current_path.append(candidate)
23                # i + 1 ensures we don't reuse the current element
24                backtrack(i + 1, current_path, remaining_target - candidate)
25                current_path.pop() # Backtrack
26
27        backtrack(0, [], target)
28        return result