Все возможные комбинации изменений

Question

Я пытаюсь вывести список списков со всеми возможными комбинациями сдачи с учетом суммы и монет. Например, учитывая количество 6 и монеты = [1,5,10], я бы получил:

[[1,1,1,1,1,1],
[1,5],
[5,1]]

Я написал что-то, что выводит правильное решение, но я не могу понять, как заставить функцию выводить решения в виде списка списков

def possible_change(n,p=[],coins = [1,5,10]):
    if n == 0:
        print(p)
        return p
    else:
        for c in coins:
            if n - c >= 0:
                possible_change(n-c,p+[c],coins=coins)

possible_change(6,coins=[1,5,10])

Как мне заставить функцию возвращать фактические списки?

Answer 1

Вы можете попробовать добавить общий список к функции и вернуть его, если n - c меньше 0 или если for loop for c in coins: является концом

def possible_change(n,p=[],coins = [1,5,10], total=[]):
    if n == 0:
        total.append(p)
    else:
        for c in coins:
            if n - c >= 0:
                print("c {}".format(c))
                possible_change(n-c,p+[c],coins=coins)
            else:
                return total
    return total

print(possible_change(6,coins=[1,5,10]))

Результат

[[1, 1, 1, 1, 1, 1], [1, 5], [5, 1]]

Answer 2

Вместо этих операторов печати просто заполните глобальный список.

sols = []
def possible_change(n,p=[],coins = [1,5,10]):
    if n == 0:
        global sols
        sols.append(p)
    else:
        for c in coins:
            if n - c >= 0:
                possible_change(n-c,p+[c],coins=coins)    

possible_change(6,coins=[1,5,10])
print(sols)

[[1, 1, 1, 1, 1, 1], [1, 5], [5, 1]]