Combination Sum II - Video Solutions

Problem Overview: Given an array of candidate numbers and a target value, find all unique combinations where the chosen numbers add up to the target. Each number can be used at most once, and the result must not contain duplicate combinations.

Approach 1: Backtracking with Sorting (O(2^n) time, O(n) space)

This problem fits naturally into a backtracking search. Start by sorting the array. Sorting groups equal numbers together, which makes it possible to skip duplicates while exploring combinations. During recursion, iterate through candidates starting from the current index, add the current value to the combination, and recursively search with the remaining target.

The key detail is duplicate handling. When iterating, if candidates[i] == candidates[i-1] and i is not the starting index of the current recursion level, skip that element. This prevents generating the same combination multiple times. The recursion stops when the target becomes zero (valid combination) or negative (invalid path). Because every element is considered once per branch, the worst‑case time complexity is O(2^n), while recursion depth requires O(n) auxiliary space.

This approach is widely used in interview problems involving subset generation with constraints. It is simple, efficient for typical input sizes, and easy to reason about once the duplicate skipping rule is understood.

Approach 2: Dynamic Programming with Combination Tracking (O(n * target * k) time, O(target * k) space)

A dynamic programming variant treats the problem as a constrained subset sum. Maintain a DP structure where dp[s] stores all unique combinations that produce sum s. Process numbers one by one and update sums in descending order so each element is used only once.

For each candidate value num, iterate sums from target down to num. For every combination in dp[s - num], append num and store the result in dp[s]. Because duplicates may exist in the input, sorting and careful set-based filtering are needed to avoid repeated combinations. The complexity depends on how many combinations are generated, represented as k.

This method works well when the target value is relatively small and you want an iterative solution rather than recursion. However, it uses more memory because it stores intermediate combinations for many sums.

Recommended for interviews: The backtracking approach is the one interviewers typically expect. It demonstrates understanding of recursion, pruning, and duplicate handling in sorted arrays. A brute-force subset enumeration shows the basic idea, but optimized backtracking with duplicate skipping shows stronger problem-solving skill and familiarity with common combination generation patterns.