Coin Change II
MediumDynamic Programming
You are given a target amount and a list of distinct coin denominations coins, with an unlimited supply of each.
Return the number of different combinations of coins that add up to exactly amount. A combination is a multiset: the order coins are picked in does not matter, so 1 + 2 and 2 + 1 are the same combination. If amount cannot be formed, return 0. An amount of 0 has exactly one combination: using no coins.
Example 1
- Input:
- amount = 6, coins = [1, 2, 3]
- Output:
- 7
- Explanation
- The combinations are 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1 and 1+1+1+1+1+1.
Example 2
- Input:
- amount = 7, coins = [2, 4]
- Output:
- 0
- Explanation
- Both coins are even, so no combination reaches the odd amount 7.
Example 3
- Input:
- amount = 0, coins = [3]
- Output:
- 1
- Explanation
- Choosing no coins is the one way to make 0.
Constraints
- 0 ≤
amount≤ 5000 - 1 ≤
coins.length≤ 300 - 1 ≤
coins[i]≤ 5000 - All values in
coinsare distinct - The answer fits in a signed 32-bit integer