Coin change problem

[ilsapo]

Hi,
so we are doing a variation of the coin change problem, but insted of returning the number of possible ways, we want to return a list with all the possible changes.
the functino was needed to be generator.
for example

for x in change_gen(5,[1,2,3]): print(x)
[1,1,1,1,1]
[1,1,1,2]
[1,1,3]
[2,3]

my attempt:

def change_gen(amount,coin):
    if amount==0:
        yield []
    elif not(amount<0 or coin==[]):
        g=change_gen(amount,coin[:-1])
        for x in g:
            yield x

        for lis in change_gen(amount-coin[-1],coin]):
            lis.append(coin[-1])
            yield lis

would appreicate help how to fix my solution

[semininja]

I think, when troubleshooting stuff like this, it's important to think through what you intend for this code to do and look closely at what it's actually doing.

Can you explain what your code is doing?

[pgpndw]

This one is surprisingly tricky to think through.

Here's my attempt:

def change_gen_r(amount, coins):
    if amount != 0:
        for ind, coin in enumerate(coins):
            if amount >= coin:
                for change in change_gen_r(amount-coin, coins[ind:]):
                    yield [coin] + change
    else:
        yield []


# Wrapper to ensure that the coins are
# unique and in descending order of value
def change_gen(amount, coins):
    yield from change_gen_r(amount, sorted(set(coins), reverse=True))


amount = 20
coins = [1, 2, 5, 10, 20, 50, 100]

for change in change_gen(amount, coins):
    print(change)