L9: Combination Sum II - Recursion, Backtracking, and Duplicate Avoidance

1. Problem Statement & Overview

In Combination Sum II, we are given a collection of candidate numbers (candidates) and a target number (target). Our task is to find all unique combinations in candidates where the candidate numbers sum up to the target.

Unlike standard subset or combination problems, this problem introduces two major constraints:

1. Single-Use Elements: Each number in candidates can only be used once in any given combination.
2. No Duplicate Combinations: The solution set must not contain duplicate combinations. Additionally, the combinations must be returned in lexicographical (sorted) order.

2. Why the Brute-Force Approach Fails

If you approach this problem using a naive subset-generation strategy (similar to Combination Sum I, but restricting element reuse to once by moving to index + 1), two major issues arise:

• Duplicate Combinations: Because the input array can contain duplicate numbers (e.g., [1, 1, 2, 5, 6, 5, 5]), exploring every index combination blindly will generate identical subsets multiple times (e.g., picking the first 1 and 2 versus the second 1 and 2).
• Overhead of Set Deduplication: A brute-force method might collect all valid combinations into a temporary data structure, push them into a HashSet to filter out duplicates, and then convert the set back into a list of lists.

The Time Complexity Trap of Brute Force

If you rely on a HashSet to eliminate duplicate combinations, inserting elements of length $K$ into a set requires logarithmic time based on the set size. For $2^N$ possible subsequences, the time complexity balloons to:

Interviewer panels heavily penalize this approach because it uses brute force plus post-processing rather than controlling generation at the recursive level. We need an optimized backtracking framework that never generates duplicates in the first place.

3. Core Mental Model & The Skip-Duplicate Strategy

To prevent generating duplicate combinations when the input array contains duplicate elements, we must structure our choices carefully.

Real-Life Analogy: Selecting Items from a Sorted Shelf

Imagine standing in front of a shelf containing items with identical price tags (duplicates), arranged neatly in ascending order. If you decide not to buy a specific item at index i, it makes zero logical sense to pick an identical item right next to it (i + 1) for the exact same slot in your basket. Doing so would create a duplicate receipt bundle.

The Decision Rules

1. Sort the Array First: Sorting (candidates) ensures that identical elements sit adjacent to each other. It also guarantees that our resulting combinations naturally form in lexicographical order.
2. Iterative Exploration at Each Level: Instead of a binary "pick or not pick" tree for every single index, we use a loop at each recursion level to explore picking one valid candidate from the remaining choices.
3. The Skip Condition: Within the recursive loop, if we encounter an element that is identical to the previous element and we are not at the starting index of our current recursion level, skip it.

4. Step-by-Step Execution Flow

Let's trace how the recursion tree explores choices without generating redundant states.

5. Backtracking Mechanics & State Restoration

Backtracking requires us to maintain a single data structure (e.g., a temporary list ds) during traversal.

1. Choose: Add the current candidate candidates[i] to ds.
2. Explore: Recursively call the function with i + 1 (since each element can be used only once) and reduce the target by candidates[i].
3. Un-choose (Backtrack): Remove the last element added to ds so that the execution frame can explore alternative branches cleanly.

// Conceptual Backtracking Flow
ds.add(candidates[i]);               // Choose
findCombinations(i + 1, target - candidates[i], candidates, ans, ds); // Explore
ds.remove(ds.size() - 1);            // Un-choose (Backtrack)

6. Complete Java Solution

Here is the complete, production-grade Java solution implementing optimal recursion and duplicate pruning.

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class CombinationSumII {
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        // Step 1: Sort the array to handle duplicates and ensure sorted output
        Arrays.sort(candidates);
        findCombinations(0, target, candidates, ans, new ArrayList<>());
        return ans;
    }
    
    private void findCombinations(int ind, int target, int[] candidates, List<List<Integer>> ans, List<Integer> ds) {
        // Base Condition: If target is met, add copy of current ds to ans
        if (target == 0) {
            ans.add(new ArrayList<>(ds));
            return;
        }
        
        for (int i = ind; i < candidates.length; i++) {
            // Skip duplicate elements at the same recursion level
            if (i > ind && candidates[i] == candidates[i - 1]) {
                continue;
            }
            
            // If current candidate exceeds remaining target, break optimization loop
            if (candidates[i] > target) {
                break;
            }
            
            // Choose
            ds.add(candidates[i]);
            
            // Explore (increment index to i + 1 because elements can only be used once)
            findCombinations(i + 1, target - candidates[i], candidates, ans, ds);
            
            // Un-choose (Backtrack)
            ds.remove(ds.size() - 1);
        }
    }
}

7. Complete C++ Solution

Here is the equivalent C++ implementation using vectors and standard library sorting.

#include <vector>
#include <algorithm>

class Solution {
private:
    void findCombinations(int ind, int target, std::vector<int>& candidates, std::vector<std::vector<int>>& ans, std::vector<int>& ds) {
        // Base Condition
        if (target == 0) {
            ans.push_back(ds);
            return;
        }
        
        for (int i = ind; i < candidates.size(); i++) {
            // Skip duplicates at the same tree level
            if (i > ind && candidates[i] == candidates[i - 1]) {
                continue;
            }
            
            // Early stopping optimization
            if (candidates[i] > target) {
                break;
            }
            
            // Choose
            ds.push_back(candidates[i]);
            
            // Explore
            findCombinations(i + 1, target - candidates[i], candidates, ans, ds);
            
            // Un-choose (Backtrack)
            ds.pop_back();
        }
    }

public:
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> ans;
        // Step 1: Sort candidates
        std::sort(candidates.begin(), candidates.end());
        std::vector<int> ds;
        findCombinations(0, target, candidates, ans, ds);
        return ans;
    }
};

8. Complexity Analysis Summary

9. Summary and Key Takeaways

• Single-Use Constraint: Always pass i + 1 into recursive calls to ensure elements are not reused.
• Duplicate Prevention: Sorting the input array is mandatory. Skip identical adjacent elements using the condition if (i > ind && candidates[i] == candidates[i - 1]) continue.
• Early Termination: Because the array is sorted, if candidates[i] > target, any subsequent element in the loop will also exceed the target, allowing us to break early.
• Lexicographical Order: Sorting at the very beginning guarantees that combinations are generated and stored in sorted order natively.
• No Extra Data Structures: Avoiding HashSet deduplication keeps memory overhead minimal and runtime optimal.