Coin Change

You get an array coins of coin values and an integer amount.

Return the smallest number of coins that add up to exactly amount.

You can use each coin value as many times as you like. If no mix of coins makes amount, return -1.

Example 1:

Input: coins = [2, 5, 10], amount = 27
Output: 4
Explanation: 27 = 10 + 10 + 5 + 2.
No three coins add up to 27.

Example 2:

Input: coins = [4, 6], amount = 9
Output: -1
Explanation: Both coin values are even.
So every sum of them is even.
9 is odd, so no mix of coins makes it.

Example 3:

Input: coins = [1, 5, 6, 9], amount = 11
Output: 2
Explanation: 11 = 5 + 6.
9 + 1 + 1 also makes 11, but that is three coins.

Constraints:

• coins holds 1 to 12 values.
• Each value is from 1 to 2³¹ - 1.
• amount is from 0 to 10,000.
• For amount = 0, the answer is 0 (no coins are needed).