40. Combination Sum II
You are given an array candidates of positive integers — repeated values are allowed — and a positive integer target. Collect every distinct combination of array elements that sums exactly to target, where each element may be used at most once. Combinations are compared as multisets of values: picking the first 1 versus the second 1 in the array does not create a new combination, so no value-for-value duplicate may appear in your answer.
Return the list in canonical form: inside each combination the values appear in non-decreasing order, and the combinations themselves are sorted in ascending lexicographic order. If nothing sums to the target, return an empty list (the raw output prints -1).
Example 1:
Input: candidates = [6, 1, 3, 2, 1, 5], target = 7
Output: [[1, 1, 2, 3], [1, 1, 5], [1, 6], [2, 5]]
Explanation: Both 1s may appear together because they are different array elements, but [1, 6] is listed once even though it can be formed with either 1 — as a multiset of values it is a single combination.
Example 2:
Input: candidates = [2, 2, 2, 4], target = 6
Output: [[2, 2, 2], [2, 4]]
Explanation: Three ways to pick two 2s and one way to pick three exist positionally, but by value they collapse to just [2, 2, 2] and [2, 4].
Constraints:
- 1 ≤ candidates.length ≤ 25
- 1 ≤ candidates[i] ≤ 50 (values may repeat)
- 1 ≤ target ≤ 30
Hints:
Sort first, then backtrack with a start index, recursing with j + 1 so an element is never reused. That alone still produces duplicate combinations whenever equal values sit next to each other — [1a, 6] and [1b, 6] both appear.
The classic dedup rule: inside one level of the recursion, skip candidates[j] when j > start and candidates[j] == candidates[j - 1]. Taking a value is always done through its *first* unused copy, so each multiset is built exactly once — no hash set needed, and the sorted DFS emits combinations already in lexicographic order.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: candidates = [6, 1, 3, 2, 1, 5], target = 7
Expected output: [[1, 1, 2, 3], [1, 1, 5], [1, 6], [2, 5]]