#322 Coin Change
You have coins in the denominations listed in coins (unlimited supply of
each) and a target amount. Return the fewest coins whose values sum to
exactly amount. If no combination of coins can hit the amount exactly,
return -1. An amount of 0 needs 0 coins.
Examples
Input
coins = [1, 2, 5], amount = 11Output
311 = 5 + 5 + 1, three coins, and nothing does it in two.
Input
coins = [2], amount = 3Output
-1Even values only; 3 is unreachable.
Input
coins = [1, 3, 4], amount = 6Output
2Greedy grabs the 4, then must take 1 + 1: three coins. The optimal 3 + 3 uses two. This is why greedy is disqualified.
Constraints
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 2³¹ − 10 ≤ amount ≤ 10⁴
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.