Combination Sum II - Video Solutions

Problem Overview: Given an integer array candidates and a target value, return all unique combinations where the chosen numbers sum to the target. Each number can be used at most once, and duplicate combinations must be avoided even if the input contains repeated values.

Approach 1: Backtracking with Sorting and Pruning (Time: O(2^n), Space: O(n))

This problem fits naturally with backtracking. Start by sorting the array so duplicates sit next to each other. Recursively build combinations while tracking the remaining target. At each step you iterate forward from the current index, choose a candidate, subtract it from the remaining target, and continue exploring deeper. If the remaining target becomes zero, you record the current path as a valid combination.

The key detail is duplicate elimination. When iterating through candidates, skip elements that are the same as the previous element at the same recursion depth (if i > start and nums[i] == nums[i-1]). Sorting enables this check and prevents generating identical combinations like [1,2,5] multiple times. Another optimization is pruning: once the current number exceeds the remaining target, you stop exploring that branch because further numbers will only be larger.

This approach works well because the search space shrinks quickly after sorting and pruning. The recursion depth is at most n, and the algorithm only explores valid candidate paths instead of brute-forcing every subset.

Approach 2: Dynamic Programming (Time: O(n * target * k), Space: O(n * target))

A dynamic programming variant can also generate combinations that sum to the target. The idea is similar to subset sum. Build a DP table where dp[s] stores combinations that produce sum s. Iterate through the candidates and update the table from target down to the candidate value to ensure each element is used only once.

When updating the table, append the current candidate to combinations that previously formed s - candidate. Because the array may contain duplicates, sorting and careful state handling are required to avoid repeated result sets. While this method systematically builds solutions, it typically consumes more memory because it stores many intermediate combinations.

The DP approach is useful when the target value is relatively small and you want a structured bottom-up solution. However, managing duplicates and combination storage makes it less common in interviews.

Recommended for interviews: The expected solution is the backtracking approach. Interviewers want to see that you recognize the subset-generation pattern, sort the array, skip duplicates, and prune early when the remaining sum becomes negative. A brute-force subset enumeration shows basic understanding, but optimized backtracking with duplicate handling demonstrates strong control of recursion and search pruning. The problem mainly tests skills in array manipulation and recursive exploration.