Combination Sum II
mediumTime: O(2^n)Space: O(n)
Signals to notice
combinations summing to target, each element used onceskip duplicate candidatessort first
Brute force first
Not applicable — enumeration with constraints.
The key insight
Sort. Backtrack from current index (no reuse). Skip candidates[i] when equal to candidates[i-1] at same level. O(2^n).
What must stay true
Sorting groups duplicates. Skipping same-value candidates at the same recursion level prevents duplicate combinations.
Easy way to go wrong
Not handling duplicates — [1,1,2] without skipping generates duplicate [1,2] combinations.