Possible combinations of coins to assemble some amount

coins.py

from bisect import bisect_right
from typing import Optional, Set


class CoinStack:
    def __init__(self):
        self._coins = []
        self._sum = 0

    def put(self, coin):
        self._coins.append(coin)
        self._sum += coin

    def take(self):
        coin = self._coins.pop(-1)
        self._sum -= coin
        return coin

    @property
    def coins(self):
        return tuple(self._coins)

    @property
    def sum(self):
        return self._sum

    @property
    def top(self):
        return self._coins[-1]


class LowerCoinIndex:
    def __init__(self, coins: Set[int]):
        self.coins = list(sorted(coins))
        self.index = {}
        rc = list(reversed(self.coins))
        for from_c, to_c in zip(rc, rc[1:]):
            self.index[from_c] = to_c
        self.index[rc[-1]] = None

    def get(self, coin: int) -> Optional[int]:
        return self.index[coin]

    def take_le(self, value: int) -> Optional[int]:
        i = bisect_right(self.coins, value)
        if i:
            return self.coins[i - 1]
        raise ValueError


def possible_payments(amount: int, coins: Set[int]):
    lc_index = LowerCoinIndex(coins)

    stack = CoinStack()

    # put biggest possible coin as first one
    stack.put(lc_index.take_le(amount))

    while True:
        if stack.sum == amount:
            yield stack.coins

            # replacing big coins with lesser ones
            while stack.sum > 0:
                coin = stack.take()
                new_coin = lc_index.get(coin)
                if new_coin is not None:
                    stack.put(new_coin)
                    break
            else:
                return
        else:
            # trying to add more coins
            new_coin = lc_index.take_le(min(amount - stack.sum, stack.top))
            if new_coin is not None:
                stack.put(new_coin)
            else:
                break


def pay(amount: int, coins: Set[int]):
    result = 0
    for _ in possible_payments(amount, coins):
        result += 1
    return result


def test():
    lc_index = LowerCoinIndex({1, 2, 5, 10})
    assert lc_index.get(5) == 2
    assert lc_index.get(1) is None

    assert lc_index.take_le(20) == 10
    assert lc_index.take_le(10) == 10
    assert lc_index.take_le(9) == 5
    assert lc_index.take_le(1) == 1

    try:
        lc_index.take_le(0)
    except ValueError:
        pass
    else:
        assert False


test()
for p in possible_payments(5, {1, 2, 5, 10, 20}):
    print(p)