hardBacktrackingPure DSA~35 min
Combination Sum Where Each Number Is Used Once
From a list of candidate values (with possible duplicates), find all unique combinations that sum to a target, using each list element at most once.
Problem
Given a collection candidates (which may contain duplicates) and a target, return all unique combinations where the chosen numbers sum to target. Each number in candidates may be used at most once in a combination; the solution set must not contain duplicate combinations.
Input
An array candidates and an integer target.
Output
A list of all unique combinations summing to target.
Constraints
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50, 1 <= target <= 30
- Duplicates are possible.
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]]
Four unique combinations sum to 8.
Example 2
Input
candidates = [2,5,2,1,2], target = 5
Output
[[1,2,2],[5]]
Two unique combinations sum to 5.