Coin Change
Intermediate
coins lists coin values (you may use each value any number of times). Return the fewest coins that add up to amount, or -1 if it is impossible.
For coins = [1, 2, 5] and amount = 11 the answer is 3 (5 + 5 + 1).
The starter code is a plain recursion. It is correct but too slow for large amounts.
Examples
Example 1
Input:
coin_change([1, 2, 5], 11)
Output:
3
Example 2
Input:
coin_change([2], 3)
Output:
-1
Constraints
0 <= len(coins) <= 121 <= coins[i] <= 100000 <= amount <= 10000
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.