Count coin combinations
You get a whole number amount and a list coins of different coin values. You have as many coins of each value as you want. Return how many different combinations of coins add up to exactly amount.
In a combination only the number of coins of each value matters, not their order: 1 + 2 and 2 + 1 are the same combination. When amount is 0 the answer is 1, the combination with no coins. When no combination works, the answer is 0.
amount = 4, coins = [1, 2, 3]Output41 + 1 + 1 + 1, 1 + 1 + 2, 2 + 2 and 1 + 3. Counting orders as different would give 7, because 1 + 1 + 2 has three orders and 1 + 3 has two.
amount = 7, coins = [2, 4]Output0Every combination of 2s and 4s adds up to an even number, and 7 is odd.
amount = 0, coins = [5]Output1Using no coins makes 0.
0 ≤ amount ≤ 5,000
1 ≤ len(coins) ≤ 300
1 ≤ coins[i] ≤ 5,000
The values in
coinsare all different.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.