выход

аюсь определить функцию, которая возвращает список всех комбинаций легальных монет, которые составляют данную сумму. Допустим, данная сумма была10 и легальные монеты были5, 2, 3, В этом случае функция должна вернуть:

[[2, 2, 2, 2, 2], [3, 3, 2, 2], [5, 3, 2], [5, 5]]

Мне удалось создать рекурсивную функцию, которая дает мне правильный результат, но печатая правильные ответы в отдельных строках и смешивая в кучуNone«S.

Как я могу вернуть правильный ответ на список юридических решений, не прерывая функцию преждевременно. Я знаю, что моя функция неэффективна. Я могу подумать о некоторых улучшениях сам, и буду реализовывать их позже.

Вот мой код:

def count_change(tot_amount, coins, used_coins=[]):

    # Sort coins and get rid of coins that are too big
    if len(used_coins) == 0:
        coins = [x for x in sorted(coins) if x <= tot_amount]

    for coin in coins:
        # If the first condition holds I want to add the printed
        # statement to a list of solution instead of printing
        if tot_amount - sum(used_coins) == coin:
            print(used_coins + [coin])
        elif tot_amount - sum(used_coins) > coin:
            print(count_change(tot_amount,
                               [x for x in coins if x <= coin],
                               used_coins + [coin]))

print(count_change(10, [5, 2, 3]))

Это вывод:

[2, 2, 2, 2, 2]
None
None
None
None
None
None
None
[3, 3, 2, 2]
None
None
None
None
None
None
[5, 3, 2]
None
[5, 5]
None
None

Ответы на вопрос(1)

Решение Вопроса

генератор, заменив теprint звонки сyield.

Я также изменил значение по умолчаниюused_coins вNone, поскольку вы не хотите, чтобы здесь был изменяемый аргумент по умолчанию. Видеть«Наименьшее удивление» и изменчивый аргумент по умолчанию для деталей.

def count_change(tot_amount, coins, used_coins=None):
    # Sort coins and get rid of coins that are too big
    if used_coins is None:
        used_coins = []
        coins = [x for x in sorted(coins) if x <= tot_amount]

    for coin in coins:
        # If the first condition holds we have a valid combination 
        if tot_amount - sum(used_coins) == coin:
            yield used_coins + [coin]
        # Otherwise, if this coin is small enough, recurse to find combinations
        # that use this coin in addition to the existing used_coins
        elif tot_amount - sum(used_coins) > coin:
            yield from count_change(tot_amount,
                               [x for x in coins if x <= coin],
                               used_coins + [coin])

for t in count_change(10, [5, 2, 3]):
    print(t)

выход

[2, 2, 2, 2, 2]
[3, 3, 2, 2]
[5, 3, 2]
[5, 5]

Если вам действительно нужен список решений, просто запустите генератор в список, например так:

seq = list(count_change(10, [5, 2, 3]))
print(seq)

выход

[[2, 2, 2, 2, 2], [3, 3, 2, 2], [5, 3, 2], [5, 5]]

Ваш ответ на вопрос