Coin partitions

Question

I am looking to obtain the partitions of coins that sum to a target amount

So I tried search online, but every single website loves to use this problem to show the benefits of dynamic programming. However, they all only show the number of ways to sum to the target, or the minimum amount of coins.

I am not interested in that, I want the actual partitions. I wrote the following code, it works as intended but is a bit scuffed. The collected_amount is incorrect, however, fixing it returns a bunch of duplicates. I "fixed" this by checking the target sum manually before yielding.

Any improvements in algorithm or structure is more than welcome =)

from typing import Annotated, Iterable, Optional
Denomination = Annotated[
 int,
 "A positive integer represeting the face value of a coin",
]
def coin_partitions(
 coins: list[Denomination],
 amount: int,
 current_coin: Denomination = -1,
 next_coin_index: int = 0,
 collected: Optional[dict[Denomination, int]] = None,
 collected_amount: int = 0,
) -> Iterable[dict[Denomination, int]]:
 """Yields denominations that sums to a target amount
 Args:
 coins (list[Denomination]): Possible denominations to choose from
 amount (int): The target amount the denominations should sum to
 current_coin (Denomination): The current coin we are iterating over
 coin_index (int): The index of the next current count
 collected (Optional[dict[Denomination, int]]): A dictionary containing the coins obtained so far
 collected_amount (int): The monetary value (sum) of the coins collected so far
 Yields:
 A dictionary reprsenting the denominations and amount to sum to target
 Examples:
 >>> partitions = coin_partitions(coins=[1,3,5], amount=12)
 >>> next(partitions)
 {5: 0, 3: 0, 1: 12}
 Which makes sense since `5 x 0 + 3 x 0 + 1 x 12 = 12`. Similarly
 >>> for partition in partitions:
 ... print(partition)
 {5: 0, 3: 1, 1: 9}
 {5: 0, 3: 2, 1: 6}
 {5: 0, 3: 3, 1: 3}
 {5: 0, 3: 4, 1: 0}
 {5: 1, 3: 0, 1: 7}
 {5: 1, 3: 1, 1: 4}
 {5: 1, 3: 2, 1: 1}
 {5: 2, 3: 0, 1: 2}
 >>> len(list(coin_partitions(coins=[1,3,5], amount=123)))
 542
 Which is possible to confirm using dynamic programming.
 """
 if collected is None:
 collected = dict()
 coins.sort(reverse=True)
 current_coin = coins[0]
 next_coin_index = 1
 if next_coin_index == len(coins):
 number = (amount - collected_amount) // current_coin
 collected[current_coin] = number
 if sum(coin * number for (coin, number) in collected.items()) == amount:
 yield collected
 return
 for i in range(1 + (amount - collected_amount) // current_coin):
 collected[current_coin] = i
 yield from coin_partitions(
 coins=coins,
 amount=amount,
 current_coin=coins[next_coin_index],
 next_coin_index=next_coin_index + 1,
 collected=collected.copy(),
 collected_amount=collected_amount + i * current_coin,
 )
if __name__ == "__main__":
 import doctest
 doctest.testmod()
 for partition in coin_partitions([1, 3, 5], amount=12):
 print(partition)

Answer 1

The readability is fine. If you cut out the documentation it's about 15 lines long, and short is almost always readable.

Replace coins.sort with sorted(coins). Don't modify arrays passed in without copying them first.

Pull out the setup logic and the final denomination into one function. Put the main recursive logic in another. Is the smallest coin always 1? If so, the final denomination logic becomes even simpler.

The performance is probably acceptable for any number of partitions you can reasonably print, though it could be improved. (Dynamic programming or LCMs)