481. Fewest Coins
You have coins of k given denominations, in unlimited supply. Print the
fewest coins that sum to exactly amount, or -1 if it cannot be done.
Taking the largest coin that fits, repeatedly, is wrong. With coins 1, 10 and 25 and an amount of 30, that rule takes 25 and then five 1s for six coins, while three 10s is the answer. The rule happens to be correct for everyday currency, which is exactly what makes it dangerous.
Unlimited supply is what separates this from the bag: the take branch stays on the same coin rather than moving past it, which is one index and a completely different problem.
Constraints - `1 ≤ k ≤ 12` - `0 ≤ amount ≤ 10000` - `1 ≤ coin[i] ≤ 10000`
Input
The first line contains two integers k and amount.
The second line contains k space-separated coin denominations.
Output
Print one integer: the fewest coins summing to amount, or -1 if it is impossible.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.