Coin Change
Part of Practice: Strings & Coins
You are given coin denominations in an array coins and a target amount. With an unlimited supply of each denomination, find the smallest number of coins whose values add up exactly to amount. If no combination reaches the amount exactly, return -1. An amount of 0 needs 0 coins.
Constraints: 1 <= coins.length <= 12, 1 <= coins[i] <= 2^31 - 1, 0 <= amount <= 10^4.
Examples
- Input:
- coins = [1, 2, 5], amount = 11
- Output:
- 3
11 = 5 + 5 + 1. Greedy happens to work here, but three coins is provably minimal.
- Input:
- coins = [2], amount = 3
- Output:
- -1
Only even totals are reachable with 2s; 3 is impossible.
- Input:
- coins = [1], amount = 0
- Output:
- 0
Zero needs no coins at all.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.