Coin change, fewest coins for an amount
You have an unlimited supply of coins in given denominations. Return the minimum number of coins whose values sum to a target amount, or -1 if no combination works.
coins = [1, 2, 5], amount = 11 -> 3 # 5 + 5 + 1
coins = [2], amount = 3 -> -1 # odd amount, only 2s
coins = [1, 2, 5], amount = 0 -> 0 # empty set
Return the fewest coins, or -1. Target .
Show a hint
The greedy "take the biggest coin that fits" fails (try coins = [1, 3, 4], amount = 6: greedy gives 4+1+1 = 3, but 3+3 = 2 is better). What is the fewest coins for every smaller amount, built up from zero?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.