Fix the memoization in my algo for the coin change challenge
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])
[]