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.
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
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.