Find the Minimum Number of Coins for an Amount

Problem Statement

You are given an integer array coins representing available coin denominations and an integer amount representing a total target sum. You may assume that you have an infinite number of each kind of coin.

Write a function to compute the minimum number of coins needed to make up that exact amount. If that amount of money cannot be made up by any combination of the coins, return -1. If the target amount is 0, return 0.

Note that the coins array may contain duplicate denominations and is not guaranteed to be sorted.

Function Signature

def min_coins(coins: list[int], amount: int) -> int:
    pass

Input and Output

• Input:
  • coins: A list of positive integers.
  • amount: A non-negative integer.
• Output: An integer representing the minimum number of coins, or -1 if impossible.

Constraints

• 1 <= len(coins) <= 100
• 1 <= coins[i] <= 10^4
• 0 <= amount <= 10^4

Examples

Example 1

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 can be formed using 5 + 5 + 1 (3 coins).

Example 2

Input: coins = [2], amount = 3
Output: -1
Explanation: The amount of 3 cannot be formed using only coins of denomination 2.

Example 3

Input: coins = [1, 2, 5], amount = 0
Output: 0
Explanation: 0 coins are needed to make an amount of 0.

Edge Cases to Consider

• amount == 0: Should always return 0, regardless of the contents of coins.
• coins containing duplicate denominations (e.g., [2, 2, 5]): Ensure duplicates do not trigger redundant computations.
• Large target amounts with no valid combination: Should terminate efficiently and return -1.