DSA Coin Change

How it works

The function assumes unlimited use of each positive integer denomination. For each target amount, it considers an earlier reachable amount plus one coin and records a predecessor coin for reconstruction. Unreachable states remain infinite, while amount zero has the empty solution. Denominations are deduplicated and a bounded target protects the teaching table from an accidental huge allocation. This contract is different from a limited-stock coin inventory.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as minimum-coins.py and run python minimum-coins.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def minimum_coins(coins, amount):
    if type(amount) is not int or not 0 <= amount <= 10000 or any(type(coin) is not int or coin < 1 for coin in coins):
        raise ValueError("Positive coins and bounded nonnegative amount required")
    coins = sorted(set(coins))
    best, previous = [float("inf")] * (amount + 1), [None] * (amount + 1)
    best[0] = 0
    for target in range(1, amount + 1):
        for coin in coins:
            if coin <= target and best[target - coin] + 1 < best[target]:
                best[target] = best[target - coin] + 1
                previous[target] = coin
    if best[amount] == float("inf"):
        return None
    result = []
    while amount:
        coin = previous[amount]
        result.append(coin)
        amount -= coin
    return result

print(minimum_coins([1, 3, 4], 6))
print(minimum_coins([4, 6], 3))
print(minimum_coins([1, 3], 0))

Expected result

[3, 3]
None
[]

The optimal six uses two threes, the impossible three returns None, and zero needs no coins. A witness must sum to the target using allowed denominations; the review checks those properties as well as the independently computed minimum count.

Time, space and assumptions

For target A and k distinct denominations, the table takes O(Ak) time and O(A+k) storage after O(k log k) ordering. The numeric target makes this a pseudo-polynomial method.