Find the Fewest Coins Needed for an Amount
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Find the Fewest Coins Needed for an Amount
Given positive coin denominations `coins` and a nonnegative integer `amount`, return the fewest coins whose values sum exactly to `amount`. You have an unlimited supply of every denomination.
If no combination can make the amount, return `-1`.
### Function
`int coinChange(vector<int>& coins, int amount)`
### Example 1
```text
Input: coins = [1,3,4], amount = 6
Output: 2
```
Two coins of value `3` make `6`. Choosing a coin of value `4` first would require two more coins of value `1`.
### Example 2
```text
Input: coins = [4,6], amount = 7
Output: -1
```
### Example 3
```text
Input: coins = [5,9], amount = 0
Output: 0
```
### Constraints
- `1 <= coins.length <= 12`.
- `1 <= coins[i] <= 2147483647`.
- `0 <= amount <= 10000`.
### Clarifications
Using the same denomination several times is allowed. The order of selected coins does not matter. Return the minimum count, not the number of combinations or a particular coin list.
### What a Strong Answer Covers
- How the proposed result is shown to be the smallest possible coin count.
- How reachable and unreachable amounts are distinguished.
- The zero amount, denominations larger than the amount, and repeated use of one denomination.
- A correctness argument and bounds tied to the amount and denomination count.
Overview: Practice finding the minimum number of coins needed to make an exact amount with unlimited supplies. Cover unreachable amounts, a zero amount, and denominations larger than the target.
