Zero To DSAZero To DSA
Privacy Policy
House RobberLongest Increasing Subsequence

Coin Change

medium
Time: O(amount * coins)
Space: O(amount)

Given an array of coin denominations and a target amount, return the fewest number of coins needed to make that amount. If impossible, return -1. You may use each coin an unlimited number of times.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= amount <= 10⁴

Examples

Input: coins = [1,2,5], amount = 11
Output: 3
5 + 5 + 1 = 11
Input: coins = [2], amount = 3
Output: -1