I believe the memoized version is slower because of the complicated code it uses to update the memo dict in the outermost else
block. It can be much simpler:
if new_sum in memo:
combi_list = memo[new_sum]
else:
combi_list = memo[new_sum] = calculate_combinations(new_sum)
for combination in combi_list:
return_list.append(combination + [denomination])
This is be much faster. With this fix, the memoized version should be faster than the non-memoized code in most cases.
There are other issues though. You will get wrong results if your denominations
list is not sorted in increasing order or if there are gaps between the denomination values. Basically, any situation that could cause the elif
case to be hit is going to give wrong results.
Here's a version of the body of the for
loop that corrects those issues:
new_sum = max_amt - denomination
if new_sum == 0:
return_list.append([max_amt]) # don't return here, to allow unsorted denominations!
elif new_sum > 0:
if new_sum in memo:
combi_list = memo[new_sum]
else:
combi_list = memo[new_sum] = calculate_combinations(new_sum)
for combination in combi_list:
return_list.append(combination + [denomination])
# do nothing for new_amt < 0
You can further simplify things though, by making each call save its own results in the memo dict, rather than relying on its caller to do so, and by combining the base case logic (for new_sum == 0
) with the memoization. I've also renamed or eliminated several of the variables:
def find_denomination_combinations_blckknght(amount, denominations):
memo = {0: [[]]} # prefill value for base case of calculate_combinations where amt==0
def calculate_combinations(amt):
if amt not in memo:
memo[amt] = []
for denomination in denominations:
new_amt = amt - denomination
if new_amt >= 0:
for combination in calculate_combinations(new_amt):
memo[amt].append(combination + [denomination])
# do nothing for new_amt < 0
return memo[amt]
return calculate_combinations(amount)
This is slightly slower, probably because of extra function calls, but the code is much simpler, with no elif
or else
cases anywhere!