Coding Interview PatternsCombination Sum II
MediumSubsets
Combination Sum II
Explanation & Solution
Description
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination. The solution set must not contain duplicate combinations.
Examples
Example 1
Input:candidates = [10,1,2,7,6,1,5], target = 8
0
10
1
1
2
2
3
7
4
6
5
1
6
5
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Explanation: These are all unique combinations that sum to 8. Note that 1 appears twice in the input so [1,1,6] is valid.
Example 2
Input:candidates = [2,5,2,1,2], target = 5
0
2
1
5
2
2
3
1
4
2
Output: [[1,2,2],[5]]
Constraints
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
Approach
Subsets pattern
1. Sort the Candidates
- Sort in ascending order so duplicates are adjacent and we can prune early when a candidate exceeds the remaining target
2. Backtrack with Start Index
- Use a
startparameter to ensure each candidate is only considered once per combination - Track
remaining(target minus current sum) to know when a valid combination is found
3. Skip Duplicates
- If
candidates[i] === candidates[i - 1]andi > start, skip this candidate to avoid generating duplicate combinations - This works because the first duplicate has already explored all combinations including that value
4. Early Termination
- If
candidates[i] > remaining, break the loop — since the array is sorted, no further candidates can help
5. Collect Valid Combinations
- When
remaining === 0, the current combination sums exactly to the target — push a copy toresult
Key Insight
- The key difference from Combination Sum I is two-fold: move to
i + 1(no reuse) and skip same-level duplicates. Sorting makes both operations efficient.
Time
O(2^n) in the worst case — each candidate is either included or excludedSpace
O(n) for the recursion stack and current combinationVisualization
Input:
Backtracking Exploration
current path
empty
No animation available
ExploringFoundBacktrack
0 steps