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.