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.
Intuition
Sort first so duplicates sit together. Then each recursive call moves to i + 1 (no reuse), and within one level you skip a candidate equal to the previous one to avoid duplicate combinations.
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
Two new twists over Combination Sum I
This variant changes two rules: each number may be used at most once, and the input may itself contain duplicates. The first is easy — recurse with i + 1 instead of i. The second is the subtle part: with duplicate candidates, naive backtracking would emit the same combination more than once, so we need a principled way to skip duplicates without missing valid answers.
Sort, so duplicates sit together
Sort the candidates first. This does double duty: it groups equal values next to each other (making duplicates detectable), and it lets us prune early — once a candidate exceeds remain, every later candidate is larger too, so we can break the loop entirely. Within one recursion level, we then skip a candidate that equals the previous one (candidates[i] == candidates[i-1] when i > start).
Why the skip rule is exactly right
The condition i > start is doing precise work: it skips a duplicate only when it would start a sibling branch at the same depth (which would regenerate an identical combination), but still allows the duplicate to be used deeper in the tree (recursing with i + 1), so combinations like [1,1,6] that legitimately use two 1s are preserved. Record a copy of the path at remain == 0, prune/break on overflow, and pop to backtrack. Worst case O(2^N).
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.