Fewest coins to make an amount
DSA, Medium
Which structure or algorithm, and what does it cost.
You have an unlimited supply of coins of some values, for example 1, 5 and 12. You get a list coins of the coin values and a whole number amount. Return the smallest number of coins that add up to exactly amount. If no combination makes the amount, return -1. If amount is 0, return 0.
Examples
Input coins = [1, 5, 12], amount = 15
Output 3
Why 5 + 5 + 5. Taking the biggest coin first (12 + 1 + 1 + 1) needs 4 coins.
Input coins = [4, 6], amount = 7
Output -1
Why Every sum of 4s and 6s is even, so 7 cannot be made.
Input coins = [3], amount = 0
Output 0
Why Edge case: the empty set of coins already makes 0.
Constraints
- 1 <= number of coin values <= 12. Each coin value is a whole number between 1 and 10,000. Values are different.
- 0 <= amount <= 10,000.
- Checking every combination of coins takes too long for these sizes.
Your answer must contain
- The approach in words, and why the greedy method (largest coin first) is not always right
- Code or pseudocode in any language
- Time and memory cost, with the reason
- A hand trace of a small example (a table of amount and answer)