Combination Sum II
Combination Sum II: given candidates (which may contain duplicates) and a target, return every unique combination summing to target. Each number may be used at most once.
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
Intuition
Combination sum ii changes two things from the original: each number may be used at most once, and the input can contain duplicates. The second change is what makes this harder, not the first.
Single use is trivial — recurse with index + 1 instead of the same index. The real problem is that duplicate values in the input produce duplicate combinations in the output. With candidates [1, 1, 2] and target 3, the two different 1s both form [1, 2], and only one should be reported.
Sorting first groups equal values together, which makes the fix positional:
- Skip a candidate when it equals the previous one and is not the first choice at this level — the earlier one already explored every combination this value can produce.
The condition is i > start && candidates[i] == candidates[i-1]. Both halves matter.
The i > start half is what distinguishes using a duplicate from re-choosing it at the same level. When i == start, this is the first pick at this position and must be allowed — otherwise legitimate combinations like [1, 1, ...] that genuinely need both copies are lost.
Writing the condition as i > 0 instead of i > start is the classic error, and it silently discards valid answers rather than producing duplicates, which makes it harder to spot.
The sorted order also enables the same pruning as the original: once a candidate exceeds the remaining target, break out of the loop entirely rather than continuing.
Each candidate may be used once, and the input contains duplicates — so the recursion advances with i + 1, and duplicates are suppressed at each level with i > start. Sorting first is what enables both the duplicate skip and the c > remain early break.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(2^N) time and O(N) space.
Separate the two changes
Single use is trivial — recurse with index + 1. The duplicates in the input are the real difficulty, since they produce identical combinations from different positions.
Sort to group equal values
Sorting places duplicates adjacent, which turns duplicate detection into a comparison with the previous element. It also enables the pruning below.
Skip repeats at the same level
Skip when i > start && candidates[i] == candidates[i-1]. The earlier copy already explored every combination this value can produce at this position.
Understand the i > start half
When i == start this is the first pick at this level and must be allowed. Writing i > 0 instead discards valid answers like [1, 1, 6] that genuinely need both copies — a silent failure, not a duplicate.
Advance the index after choosing
Recurse with i + 1 so each element is used at most once. This is the only structural difference from the unlimited-reuse original.
Prune on the sorted order
Once a candidate exceeds the remaining target, every later one does too — break out of the loop rather than continuing through candidates that cannot fit.
Cost of the search
With n candidates each taken or skipped, the tree is O(2^n) in the worst case, times O(target/min) to copy each result. Space is O(n) for the recursion and path.
Solution & live demo
Common pitfalls
Skipping duplicates without the i > start guard
if candidates[i] == candidates[i-1]:
continueif i > start and candidates[i] == candidates[i-1]:
continueLegitimate combinations contain repeated values — [1, 1, 6] is valid when the input has two 1s. The guard suppresses only repeats at the same recursion depth, which are the ones that generate identical combinations.
Recursing with i instead of i + 1
backtrack(i, remain - c, path)
backtrack(i + 1, remain - c, path)
That's the Combination Sum I rule, where each number may be reused unlimited times. Here each array element may be used at most once, so the next level must start past the index just consumed.
Appending path instead of a copy
res.append(path)
res.append(path[:])
path is mutated in place by every subsequent append/pop, so all stored references end up pointing at the same eventually-empty list. Backtracking always requires snapshotting the state you record.
Edge cases
The i > start and c == prev skip ensures the two 1s don't create identical combinations.
Every branch is pruned or exhausted, leaving an empty result.
Because the list is sorted, once c > remain the remaining candidates are larger too, so the loop can stop early.