615. Reusable Coins to Target
A vending machine accepts coins of several values, and the customer owns an unlimited supply of every value. The array candidates lists the distinct coin values. The customer wants to pay exactly target.
Return every different multiset of coins whose values add up to target. Two payments are the same when each coin value is used the same number of times. The payments may be returned in any order, and the coins inside a payment may be in any order. If no payment is possible, return an empty array.
Example 1
- Input:
- candidates = [3,5], target = 11
- Output:
- [[3,3,5]]
- Explanation:
Only
[3, 3, 5]works: two 3-coins and one 5-coin.
Example 2
- Input:
- candidates = [4,6], target = 5
- Output:
- []
- Explanation:
No combination of 4s and 6s reaches 5, so the answer is empty.
Example 3
- Input:
- candidates = [2,3,7], target = 9
- Output:
- [[2,2,2,3],[2,7],[3,3,3]]
- Explanation:
Three payments exist:
[2, 2, 2, 3],[3, 3, 3]and[2, 7].
Constraints
- 1 ≤
candidates.length≤ 6 - 2 ≤
candidates[i]≤ 20, all values distinct - 1 ≤
target≤ 24
With these limits the answer is small enough to return in full.
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
Expected complexity
- Time
- O(number of payments * target)
- Space
- O(target)