Skip to main content

Coin Change

Question​

Given a set of coins and a total amount of money, determine the minimum number of coins needed to make up that amount.

Example 1
Input: coins = [1, 2, 5], amount = 11
Output: [5, 5, 1]

Solution​

all//Coin Change.py


def change(coins, total):
    minCoins = total
    if total in coins:
        return 1
    else:
        for i in [c for c in coins if c <= total]:
            numCoins = 1 + change(coins, total-i)
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins

coins = [1, 5, 10, 25]
total = 63

print("Minimum coins required is", change(coins, total))