0

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.

Optimesh
  • 422
  • 1
  • 6
  • 18

2 Answers2

2

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])
[]
user2390182
  • 72,016
  • 6
  • 67
  • 89
  • Thanks for your reply. I'm trying to understand how this works, in the sense of what component makes sure all unique combinations of the same tuple of coins that can be used to reach the target are included. It's not straightforward to me. In the meanwhile, wanted to say thanks. – Optimesh Jan 02 '18 at 12:43
  • Yup, understanding such a recursive implementation can be challenging. You should add some debugging print statements. But ultimately, the simplicity is rather beuatiful ;) – user2390182 Jan 02 '18 at 12:47
  • What collects all solutions is the fact that it loops over all coins and combines each coin with the recursive solutions for the amount without that coin. It collects all the resulting combinations in `sols`. – user2390182 Jan 02 '18 at 12:51
0

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.

Tzahi T
  • 346
  • 3
  • 11
  • I'm not sure I follow. The problem is that since there was already a solution for d[10], any other solutions were rejected. The order of the list, IIUC, only changes (or can change) which solution got in and which was/were left out. The above solution is based on a solution I wrote without memoization. The [c for c in coins if c<=i] condition is there. That code produces the same results as one of the available dynamic programming solutions you can find online (e.g. what I linked to above). Thanks for your reply. – Optimesh Jan 02 '18 at 12:26
  • I was trying to explain what happens in the first time you try to calculate d[10] - There is no solution yet - why you get only 1 solution? This is because in the previous step, you only had coins of size 5 left, and this is because your coins are ordered from small to big. Maybe some sort of illustration will help: At first you want to calculate d[20] and you have coins (5,10), now you use coin 5 (because it is the first in your list of coins), and then you call d[15] with only coins of type (5) available (`c<=i`) . then d[10] with (5) and son on. Thats why you get only 1 solution for d[10] . – Tzahi T Jan 06 '18 at 21:58