Combination sum II

Problem Given candidate numbers (may contain duplicates) and a target, return all unique combinations summing to the target; each candidate may be used at most once.

Input / Output

• Input: int array candidates, int target. Output: list of unique combinations.

Constraints

• Up to 100 candidates, target <= 30 (classic); output must contain no duplicate combinations.

Example

• candidates = [10,1,2,7,6,1,5], target = 8 → [[1,1,6],[1,2,5],[1,7],[2,6]].

Expected approach

• Sort, then backtrack: at each depth iterate candidates from the current start index; skip nums[i] == nums[i−1] when i > start (same-level dedupe — the crux vs Combination Sum I); recurse with i+1 (single use) and prune when the value exceeds the remaining target. Sorting + same-level skip guarantees uniqueness without a set. Exponential worst case; pruning keeps it practical. Contrast with Combination Sum I (unlimited reuse → recurse with i).