Coin Change

You have coins of the values in coins, as many of each as you like. Return the fewest coins that add up to exactly amount, or -1 if no combination does. An amount of 0 needs 0 coins.

Constraints

  • 1 ≤ length of coins ≤ 12
  • 1 ≤ coins[i] ≤ 100,000, all different
  • 0 ≤ amount ≤ 10,000

Example 1

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

5 + 5 + 1.

Example 2

Input
coins = [2]
amount = 3
Output
-1
Why:

Coins of 2 only make even amounts.

Example 3

Input
coins = [1]
amount = 0
Output
0
Why:

Nothing to pay.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –