coins

coins.py

data = {}
dmin = {'min': 1500}


def get_coins(coins, total, current_sum, acc):
    if len(coins) == 0 and total > 0:
        return
    if total in data and total > 0:
        acc.extend(data[total])
        total -= sum(data[total])
    if total == 0:
        print("\n" + "=" * 100 + "\n")
        print(len(acc))
        print("\n" + "*" * 100 + "\n")
        print(acc)
        print("\n" + "=" * 100 + "\n")
        dmin['min'] = len(acc)

    for c in coins:
        if c <= total:
            acc2 = acc.copy()
            acc2.append(c)
            current_sum += c
            if current_sum in data:
                if len(data[current_sum]) > len(acc2):
                    data[current_sum] = acc2
            else:
                data[current_sum] = acc2
            get_coins(coins, total - c, current_sum, acc2)
        if len(coins) > 1:
            without = coins.copy()
            without.remove(c)
            get_coins(without, total, current_sum, acc)

get_coins([200, 100, 50, 25, 15, 10, 5, 2], 1500, 0, [])