Pick Each Number At Most Once to Reach a Target Sum
Implement combinationsUsingEachOnce
You're given an array of positive integers,
candidates, which may hold repeated values, and a target. Find every distinct combination of values that sums exactly to target — this time each position in the array can be used at most once, and even though positions repeat values, the result must not contain the same value-combination twice.
Since each position is used 0 or 1 times, every combination is really a subset — brute force can enumerate all 2ⁿ of them and filter by sum, but has to actively watch for and discard duplicates that arise from picking different positions that happen to share a value. Sorting first turns that after-the-fact cleanup into a cheap, built-in check: equal values end up adjacent, so a single neighbor comparison at each step is enough to skip a duplicate before it's ever explored.
Example 1:
Input: candidates = [4,4,2,1,3], target = 7
Output: [[3,4],[1,2,4]]
Example 2:
Input: candidates = [5,5,5], target = 10
Output: [[5,5]]
Example 3:
Input: candidates = [9,9], target = 3
Output: []
+ 8 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ candidates.length ≤ 15 - ●
1 ≤ candidates[i] ≤ 25, and values may repeat within candidates - ●
1 ≤ target ≤ 35 - ●
Each position in candidates may be used at most once per combination
candidates =
[4, 4, 2, 1, 3]
target =
7