Dynamic Programming - Number of ways to calculate sum using a set of integers

Question

I went through this question

Number of ways to add up to a sum S with N numbers Find all ways to sum given number (with repetitions allowed) from given set

Did not quite understand the answers there,

I wrote two methods to solve a question:

Find the number of ways you can reach a sum S using numbers N (repetitions allowed)

eg. sum = 4 and numbers = 1,2,3 answer is 1111, 22, 1122, 31 , 13, 1212, 2112, 2212

in One method I use memoization and in the other I do not. Somehow in my machine the memoize version runs WAY slower than the non memoized version

Both of the solutions work.

Memoized Version:

def find_denomination_combinations(amount, denominations):
    memo = {}

    def calculate_combinations(max_amt):
        return_list = list()

        for denomination in denominations:
            new_sum = max_amt - denomination
            if new_sum == 0:
                return_list.append([max_amt])
                return return_list
            elif new_sum < 0:
                return [[]]
            else:
                if new_sum in memo:
                    combi_list = memo[new_sum]
                else:
                    combi_list = calculate_combinations(new_sum)
                for combination in combi_list:
                    if new_sum in memo and combination[:] not in memo[new_sum]:
                        memo[new_sum].append(combination[:])
                    else:
                        memo[new_sum] = []
                        memo[new_sum].append(combination[:])
                    combination.append(denomination)
                    return_list.append(combination)
        return return_list

    result = calculate_combinations(amount)
    return result

Non Memoized Version

def find_denomination_combinations_nmemo(amount, denominations):

    def calculate_combinations(max_amt):
        return_list = list()

        for denomination in denominations:
            new_sum = max_amt - denomination
            if new_sum == 0:
                return_list.append([max_amt])
                return return_list
            elif new_sum < 0:
                return [[]]
            else:
                combi_list = calculate_combinations(new_sum)
                for combination in combi_list:
                    combination.append(denomination)
                    return_list.append(combination)
        return return_list

    result = calculate_combinations(amount)
    return result

My algorithm is :

[T(sum-D)] for each D where D belongs to given set of integers

If input sum = 16 and set of integers = [1,2,3]

Non memoized version runs in 0.3 seconds , memoized version takes 5 seconds

Answer 1

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!