Description
Given a collection of candidate numbers and a target number, find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once.
Examples
candidates = [10,1,2,7,6,1,5], target = 8[[1,1,6],[1,2,5],[1,7],[2,6]]All unique combinations that sum to 8.
candidates = [4,4,2,1,4,2,2,1,3], target = 6[[1,1,4],[1,2,3],[2,2,2],[2,4]]This example demonstrates handling multiple duplicates of the same numbers. The array contains three 4's, three 2's, and two 1's. Searching finds all unique combinations: [1,1,4] uses both 1's and one 4, [1,2,3] uses one of each, [2,2,2] uses all three 2's, and [2,4] uses one 2 and one 4. Duplicates in the input allow for combinations with repeated values, but the output eliminates duplicate combinations.
candidates = [3,1,3,5,1,1], target = 4[[1,3],[1,1,1,1]]Sorting candidates gives [1,1,1,3,3,5]. Two unique combinations sum to 4: [1,3] (using one 1 and one 3) and [1,1,1,1] is not possible since there are only three 1's. The valid combinations are [1,3] and [1,1,1,1] — but with three 1's available, [1,1,1,1] is invalid, leaving [1,3] and [1,1,1,1] if four 1's exist. The output [[1,3],[1,1,1,1]] assumes sufficient duplicates.
Constraints
- •
1 ≤ candidates.length ≤ 100 - •
1 ≤ candidates[i] ≤ 50 - •
1 ≤ target ≤ 30