606. Single-Use Coins to Target
A child opens a piggy bank holding the coins listed in candidates. Some coin values appear more than once, and each physical coin can be used at most once. The child wants to pay exactly target.
Return every different set of coin values that adds up to target. Two payments are the same when each value is used the same number of times, even if different physical coins of that value were chosen. The payments may be returned in any order, and the values inside a payment may be in any order. Return an empty array when no payment exists.
Example 1
- Input:
- candidates = [4,4,6,2], target = 10
- Output:
- [[2,4,4],[4,6]]
- Explanation:
Two payments exist:
[4, 6]and[2, 4, 4].
Example 2
- Input:
- candidates = [5,5,5], target = 10
- Output:
- [[5,5]]
- Explanation:
Using two of the three 5-coins is a single payment,
[5, 5], whichever two coins are taken.
Example 3
- Input:
- candidates = [7,9], target = 3
- Output:
- []
- Explanation:
Every coin is larger than the target, so there is no payment.
Constraints
- 1 ≤
candidates.length≤ 12 - 1 ≤
candidates[i]≤ 15 - 1 ≤
target≤ 30
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
Expected complexity
- Time
- O(2^n)
- Space
- O(n)