Combination Sum II

Problem

You are given an array of positive integers candidates, which may contain repeated values, and a target integer target. Return every distinct combination of candidates that sums to target, where each array position may be used at most once. Two combinations are the same if they contain the same values with the same multiplicities. Output order does not matter.

• Up to 80 candidate numbers, which may repeat.
• Each candidate is a positive integer up to 45.
• Target is a positive integer up to 35.

Examples

• candidates = [9, 4, 3, 8, 5, 3, 6], target = 9 → [[3,6], [4,5], [9]]. The two 3s are different positions but [3,6] built from either one is the same combination.
• candidates = [3, 6, 3, 2, 3], target = 6 → [[3,3], [6]].
• candidates = [4, 4], target = 9 → [].

Hints

1. Start from the Combination Sum solution. Which single change enforces "each position at most once"?
2. Now sort the input and look at what happens with [1, 1, 7] and target 8. Where does the duplicate come from, and at which level of recursion?
3. Advance the start index to i + 1, and skip candidates[i] when i > start and candidates[i] == candidates[i-1].