Coin Change
Problem statement
Given positive coin denominations and a target amount, return the fewest coins needed to make that amount. You may use each denomination any number of times.
Return -1 if the amount cannot be made. Amount zero needs no coins. Denominations may be unordered or repeated; repeated denominations do not provide extra restrictions.
Function
coinChange(coins: int[], amount: int) → intExamples
Example 1
coins = [1,3,4]amount = 6return = 2Use 3 + 3, which needs two coins. No single denomination equals six, so fewer than two coins is impossible. A greedy choice of four would need three coins.
Example 2
coins = [4,6]amount = 5return = -1Every available coin is even, so every sum is even. Five cannot be made; return -1.
Constraints
1 <= coins.length <= 121 <= coins[i] <= 1000 <= amount <= 1000