182. Combination Sum II

Medium · Backtracking

Given an array of integers `candidates` and an integer `target`, find all unique combinations in `candidates` where the sum equals `target`. Each number in `candidates` may only be used once in each combination.

The solution set must not contain duplicate combinations. If there are multiple valid combinations, return them in lexicographic order (each combination sorted ascending, combinations sorted lexicographically).

Examples

Example 1
Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Explanation: Each combination sums to 8. Duplicates like [1, 1, 6] appear only once even though there are two 1's in the input. The result is sorted lexicographically.

Example 2
Input: candidates = [2, 5, 2, 1, 2], target = 5
Output: [[1, 2, 2], [5]]
Explanation: We can use each element at most once. [1, 2, 2] uses two of the three 2's. [5] is a single element that equals the target.

Constraints

• Standard input/output constraints apply