noodleProblems/
Coin Change
#154

Coin Change

AlgorithmmediumArrayDynamic ProgrammingBreadth First Search

You have an unlimited supply of each denomination in coins (an array of distinct positive integers), and you want to make up exactly amount using as few coins as possible.

Given coins and amount, return the fewest coins needed to total exactly amount. If no combination of the given coins sums to amount exactly, return -1.

Example cases

  • three coins
    in coins = [1,2,5], amount = 11
    out 3
    11 = 5 + 5 + 1, three coins — no combination of these coins does better.
  • impossible with an even-only coin
    in coins = [2], amount = 3
    out -1
    Every combination of 2s is even, so an odd amount like 3 can never be reached.
  • zero amount needs zero coins
    in coins = [1], amount = 0
    out 0

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
  • coins contains no duplicate values
Saved
coins =
[1,2,5]
amount =
11