Combination Sum II
Part of Practice: Duplicates & Grids
Given a list of candidate numbers (which may contain duplicates) and a target, return every unique combination of candidates summing exactly to the target — but now each array element may be used at most once. Combinations that use the same multiset of values must appear only once, even if they were formed from different copies in the array.
Up to 100 candidates, each between 1 and 50, target up to 30. Contrast with Combination Sum I: there, elements were distinct and reusable; here they can repeat in the input but each copy is single-use.
Examples
- Input:
- candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
- Output:
- [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
[1, 1, 6] uses both copies of 1 — legal, they are different array elements. But [1, 7] appears once even though either copy of 1 could form it.
- Input:
- candidates = [2, 5, 2, 1, 2], target = 5
- Output:
- [[1, 2, 2], [5]]
Two of the three 2s pair with the 1; the three ways of choosing which two copies collapse into a single result.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.