Coin Change: Count the Ways
Intermediate
coins are the coin values, each available without limit. Return the number of different combinations of coins that add up to amount (the order does not matter: 1+2 and 2+1 are the same). Return the answer modulo 10**9 + 7.
For amount = 5 and coins = [1, 2, 5] the answer is 4.
Examples
Example 1
Input:
count_change(5, [1, 2, 5])
Output:
4
Example 2
Input:
count_change(3, [2])
Output:
0
Constraints
0 <= len(coins) <= 1001 <= coins[i] <= 5000, all different0 <= amount <= 100000
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingsequences-and-counting
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.