Given a set of coin denominations and a target amount, determine the minimum number of coins needed to make up that amount.

You may assume that there is an unlimited supply of coins of each denomination. If it’s not possible to make up the amount, return -1.

Function Signature:

from typing import List

def coin_change(coins: List[int], amount: int) -> int:
    """
    Determine the minimum number of coins needed to make up the target amount.

    Parameters:
    - coins: A list of coin denominations.
    - amount: The target amount to make up.

    Returns:
    - int: The minimum number of coins needed, or -1 if not possible.
    """
    # Your code here

Example:

print(coin_change([1, 2, 5], 11))  # Output: 3 (11 = 5 + 5 + 1)
print(coin_change([2], 3))         # Output: -1 (Not possible)
print(coin_change([1], 0))         # Output: 0 (0 amount needs 0 coins)
print(coin_change([1], 1))         # Output: 1 (1 amount needs 1 coin)

Note:

  • You may assume that the denominations are sorted in ascending order.

Instructions:

  • Write the coin_change function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊