Coin Change in Python

You are given a list coins of coin values and an integer amount, a total sum of money.

Return the fewest number of coins that you need to make up exactly amount. If no combination of the coins adds up to amount, return -1.

You may use each coin value as many times as you want.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1. Two coins are not enough: the largest sum of two coins is 5 + 5 = 10.

Example 2:

Input: coins = [2], amount = 3
Output: -1
Explanation: Coins of 2 only make even sums, so 3 can't be made.

Example 3:

Input: coins = [1, 3, 4], amount = 6
Output: 2
Explanation: 6 = 3 + 3. Always taking the largest coin that still fits gives 4 + 1 + 1, three coins,
so that shortcut doesn't always find the fewest.

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104 (when amount is 0, the answer is 0: no coins at all)