My take on an algorithm to generate all possible coins combinations that add up to given amount (a.k.a. vending machine change problem)

coins.py

"""
This module provides functions for splitting an amount into coins using given denominations.

The problem of generating change for a given amount, also known as the vending machine change problem (a special case of the knapsack problem), involves finding all possible combinations of coins that add up to a given amount.
"""
import functools


def split_iter(amount: int, denominations: tuple[int]):
    if not denominations or amount < 0:
        return
    remaining, denomination = amount, denominations[0]
    coins = []
    while remaining >= denomination:
        assert remaining >= 0
        for other_coins in split(remaining, denominations[1:]):
            yield (*coins, *other_coins)
        remaining -= denomination
        coins.append(denomination)
    if remaining == 0:
        yield tuple(coins)


@functools.lru_cache(maxsize=None)
def split(amount: int, denominations: tuple[int]):
    return tuple(split_iter(amount, denominations))


def _format_result(result: tuple[int]) -> str:
    # Output a string in the format "1x25c 1x10c 1x5c 3x1c"
    counts = {coin: result.count(coin) for coin in set(result)}
    return " ".join(
        f"{count}x{coin}c" for coin, count in sorted(counts.items(), reverse=True)
    )


if __name__ == "__main__":
    def main():
        results = split(100, (50, 25, 10, 5, 1))
        for result in results:
            print(_format_result(result))
        print(len(results))

    main()