Find the minimum number of coins needed to make a target amount using unlimited copies of the given denominations.
Problem
You are given an array of coin denominations and a target amount. Each denomination can be used any number of times.
Return the minimum number of coins required to make exactly the target amount. If it is impossible to form the amount, return -1.
You may assume every coin value is a positive integer.
Intuition-friendly restatement
Choose coins with repetition allowed so that their sum is exactly the target. Among all valid choices, minimize the number of coins used.
Input Format
- An integer array
coinscontaining the available denominations. - An integer
amountrepresenting the target sum.
Output Format
- Return a single integer: the fewest number of coins needed to make
amount, or-1if no combination works.
Constraints
1 <= coins.length1 <= coins[i]0 <= amount- Coin values are positive integers.
- Use unlimited copies of each coin denomination.
Example 1
Input
coins = [1,2,5], amount = 11
Output
3
Explanation
One optimal way is 5 + 5 + 1, which uses 3 coins.
Example 2
Input
coins = [2], amount = 3
Output
-1
Explanation
It is impossible to form 3 using only coins of value 2.
Show 1 more example
Example 3
Input
coins = [1], amount = 0
Output
0
Explanation
No coins are needed to make amount 0.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.