pythonrecursioncoin-change

recursive coin change problem - count permutations


Given a list of coins and a positive integer n>0 I need to find the number of permutations which sum up to n. Each coin on the list can be used many times. for example - given the following list: lst = [1,3,4] and n=4, the function should return 4: for : [1,1,1,1], [1,3], [3,1] and [4]. I was asked to give a reursive solution. I know how to write a recursive code which counts the number of combinations, but I don't know how to write the code which counts the number of permutations.

This is my code:

def coin_change(lst, n):
if n == 0:
    return 1
if len(lst) == 0:
    return 0
if n<0:
    return 0

return coin_change(lst, n-lst[0]) + coin_change(lst[1:], n)

Thanks


Solution

  • You have some issues. You keep trying to reduce the list, but because repeats are allowed, you can't do that. You have to try the whole list every time, until the sum exceeds the count. This does what you ask:

    track = []
    def coin_change(lst, n, sofar=[]):
        if sum(sofar) == n:
            print("winner", sofar)
            track.append( sofar )
            return
        if sum(sofar) > n:
            return
        for i in lst:
            coin_change( lst, n, sofar+[i] )
        return track
    
    print(coin_change([1,3,4], 4))
    

    Output:

    winner [1, 1, 1, 1]
    winner [1, 3]
    winner [3, 1]
    winner [4]
    [[1, 1, 1, 1], [1, 3], [3, 1], [4]]
    

    An alternate approach would use yield to generate the winners and yield from to pass through winners from the inner calls.