Fix the memoization in my algo for the coin change challenge

Question

I know there are many threads about this challenge, but before marking as duplicate, please read on.

Need to find all the different ways to make change, given a list of coins. I wrote a solution with recursion that works, but is very inefficient. I want to add memoization. I know there are other approaches (e..g here) to solve it, but for my understanding of how things work, I'm seeking your help fixing the problem I found with my solution.

First, here is the code:

d = {}

def make_change(n, coins):
    print n

    # base case
    if n < 0:
        print 'Nope'
        print '_'*40
        return 0

    if n == 0:
        print 'yay'
        print '_'*40
        return 1

    if n in d:
        return d[n]


    else:
        c = 0
        for i in coins:
            print 'i = ', i
            c += make_change(n-i, [c for c in coins if c<=i])  # https://stackoverflow.com/a/33425875/5056689

    d[n] = c
    return c


make_change(20, [5,10])

This returns 2 solutions, and the print statements show that the solutions are (5,5,5,5) and (10,10). The third possible solution (10,5,5) isn't included, because 10 is already in the keys.

So, how do I keep a dict with the number of unique ways to get to a certain target, without actually keeping track of all solutions, which would defeat the purpose.

Appreciate your help.

Answer 1

I think you don't have your logic completely straight. You should collect solutions for each amount. Also it makes sense to use both n and coins for memoization while only allowing coins that are not greater than the current coin in order not to generate permutations of the same change:

from collections import defaultdict
d = defaultdict(dict)

def make_change(n, coins):
    # base cases
    if n < 0:
        return []  # no possible solution
    if n == 0:
        return [[]]  # one solution: empty list
    # recursion
    sols = []  # solutions are to be collected
    # make hashable memo key, and guarantee to start with the bigger coins
    tpl = tuple(sorted(coins, reverse=True))  
    if tpl not in d[n]:
         for c in tpl:
             # Only allow coins <= c for the recursion, not to get permutations
             # of the same change, e.g. [10, 5] and [5, 10]
             for sol in make_change(n-c, [x for x in tpl if x <= c]):
                 sols.append([c] + sol)
         d[n][tpl] = sols        
    return d[n][tpl]

>>> make_change(20, [10, 5])
[[10, 10], [10, 5, 5], [5, 5, 5, 5]]
>>> make_change(25, [10, 5])
[[10, 10, 5], [10, 5, 5, 5], [5, 5, 5, 5, 5]]
>>> make_change(30, [10, 5])
[[10, 10, 10], [10, 10, 5, 5], [10, 5, 5, 5, 5], [5, 5, 5, 5, 5, 5]]
>>> make_change(27, [10, 5])
[]

Answer 2

Just to clear things out (can't comment - sorry), the line

c += make_change(n-i, [c for c in coins if c<=i])

allows the next call in the recursion to use only coins that are smaller than the one you used at the current step. This makes sense if your coins are ordered from the biggest to the smallest (as in schwobaseggl answer) but trims off solutions otherwise. What happend in your case - is so: when computing d[10], because the first coin used is 5, you eliminated the option to use a coin of value 10, and thus got only one solution for giving a change of 10 - a (5,5) change.

For easier debugging - you should print the whole (small) table 'd', instead of all those arguments you printed in the middle of your code.