DSA problem
Combination Sum II
Given a collection of candidate numbers candidates (which may contain duplicates) 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, and the solution set must not contain duplicate combinations.
This problem combines two complications: (1) each input number can be used at most once (unlike Combination Sum, which allowed unlimited reuse), and (2) the input itself may contain duplicates that should not be allowed to produce duplicate combinations in the output. A naive search would generate the multiset of subsets and then deduplicate — wasteful when the input is large.
The standard fix is sort + skip. Sort the candidates so equal values sit in contiguous runs. In the backtracking loop iterate i from start; skip the branch when i > start && candidates[i] == candidates[i - 1] because that same value already started a sub-tree at the same recursion depth. This is the classic same-level dedupe rule.
Because each candidate can be used at most once, the recursive call advances the index to i + 1 (not i). Combined with the duplicate-skip rule, every multiset that sums to target appears in the results exactly once. With sorted candidates we also get a clean early-exit: once candidates[i] > remaining, every later index is even larger, so break. Time complexity is O(2^N) worst case (size of the power set), space O(N) for recursion.
Examples
candidates = [10,1,2,7,6,1,5], target = 8[[1,1,6],[1,2,5],[1,7],[2,6]]candidates = [2,5,2,1,2], target = 5[[1,2,2],[5]]candidates = [1,1,1,1], target = 3[[1,1,1]]Constraints
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
- The input may contain duplicate values.
- Each number in candidates may be used at most once in a combination.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.