Fewest Coins at the Till

medium

A till has unlimited stock of certain coin denominations. A cashier must hand back exactly amount in change using as few coins as possible.

Given the list coins and the target amount, return the minimum number of coins that sum exactly to amount, or -1 if no combination works. An amount of 0 needs 0 coins.

Example 1

in coins = [1, 2, 5], amount = 11

out 3

5 + 5 + 1.

Example 2

in coins = [2], amount = 3

out -1

Even sums only — 3 is unreachable.

Constraints

· 1 <= len(coins) <= 12
· 1 <= coins[i] <= 1000
· 0 <= amount <= 1000