Find all unique combinations of numbers that add up to a target, using each input number at most once.
Given an array of candidate numbers and a target value, return all unique combinations where the chosen numbers sum to the target.
Each number in the array may be used at most once in a combination. The result must not contain duplicate combinations, even if the input contains repeated numbers.
Return the combinations in any order.
Input Format
- An integer array
candidates - An integer
target
Output Format
- Return a list of all unique combinations
- Each combination is a list of integers whose sum is exactly
target
Constraints
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30- The input may contain duplicate values
- Each candidate can be chosen at most once
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
The valid unique combinations that sum to 8 are listed above. Notice that [1,7] appears only once even though there are two 1s in the input.
Example 2
Input
candidates = [2,5,2,1,2], target = 5
Output
[[1,2,2],[5]]
Explanation
Use each candidate at most once, and avoid duplicate combinations caused by repeated 2s.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.