Coin Change

You are given an integer array coins representing different coin denominations and an integer amount representing the total amount of money.

Your task is to find the minimum number of coins required to make up the given amount.

You may use each coin denomination unlimited times.

If it is not possible to make the amount using the given coins, return -1.

📥 Input

• An integer array coins

• An integer amount

📤 Output

Return the fewest number of coins needed to make the given amount. If the amount cannot be formed, return -1.

🧪 Example 1

Input

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

Output

3

Explanation

The minimum number of coins required is:

11 = 5 + 5 + 1

So, the answer is 3.

Constraints

• 1 ≤ coins.length ≤ 12

• 1 ≤ coins[i] ≤ 2³¹ − 1

• 0 ≤ amount ≤ 10⁴

• All values in coins are unique