coins lists the coin values available, and each value can be used as many times as you like. Return the smallest number of coins that add up to exactly amount.
If amount cannot be reached exactly, return -1.
Example 1
Input
coins = [1, 5, 6], amount = 10
Output
2
Explanation
5 + 5 uses two coins, and no single coin is worth 10. Grabbing the biggest coin first does worse: 6 leaves 4, which takes four 1s, five coins in all.
Example 2
Input
coins = [4, 6], amount = 7
Output
-1
Explanation
every sum of 4s and 6s is even, so 7 can never be made.
Example 3
Input
coins = [5], amount = 0
Output
0
Explanation
an amount of 0 needs no coins.
Constraints:
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.