Coin Change

Medium

Given an array coins (passed as nums) and an integer amount (passed as target), return the fewest coins needed to make up that amount, or -1 if impossible. You have unlimited coins of each type.

Example 1

Input:  coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1.

Example 2

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

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4