recursive coin change problem - count permutations

Question

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

Answer 1

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.