Memoization Practice

Question

I am working on memoization practice in Python. The first 4 calls for the recursive function were solved immediately, but the final call takes too long to compute which is what I am trying to memoize. The output for my attempted memoized code solved the first 4 calls immediately, but the final call is still taking the same amount of time to compute. Is there something I am implementing wrong in my memoized code? I appreciate any help thank you!

Prompt: Write a function 'howSum(targetSum, numbers)' that takes in a targetSum and an array of numbers as arguments. The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the targetSum, then return null. If there are multiple combinations possible, you may return any single one.

Here's my implementation of the memoized code and recursive function for quick reference:

def howSum(target_num, listt, memo={}):
#if target_num in memo: return memo[target_num]
    if target_num == 0: return []
    if target_num < 0: return None
    for num in listt:
        remainder = target_num - num
        remainder_result = howSum(remainder, listt, memo)
        if remainder_result is not None:
            memo[target_num]= *remainder_result, num
            return memo[target_num]
    memo[target_num] = None
    return None

def howSum(target_num, listt):
    if target_num == 0: return []
    if target_num < 0: return None
    for num in listt:
        remainder = target_num - num
        remainder_result = howSum(remainder, listt)
        if remainder_result is not None:
            return *remainder_result, num
    return None

print(howSum(7, {2, 3}))
print(howSum(7, {5, 3, 4, 7}))
print(howSum(7, {2, 4}))
print(howSum(8, {2, 3, 5}))
print(howSum(300, {7, 14}))

Answer 1

Some issues:

• The first function is overwritten by the second, so you actually only use the second. Hence, there is no memoization happening
• The assignment says that your function should take an array, but you provide it a set. {2, 3} is a set in Python, while [2, 3] is a list.

If the first function were used:

• It has a commented line that is actually needed.
• It takes an argument that is initialised once (only once!) with ={}. This means that if your main code makes multiple calls (like in your example), memo will not be reset between calls, and therefore the results will be wrong.

So, use a different name for the first function and remove the initial value for memo. Avoid the repetition of code in the second function, and just let it call the first one, making sure it passes an empty memo dictionary:

def howSumRec(target_num, listt, memo):
    if target_num in memo: 
        return memo[target_num]
    if target_num == 0:
        return []
    if target_num < 0: 
        return None
    for num in listt:
        remainder = target_num - num
        remainder_result = howSumRec(remainder, listt, memo)
        if remainder_result is not None:
            memo[target_num]= *remainder_result, num
            return memo[target_num]
    memo[target_num] = None
    return None

def howSum(target_num, listt):
    return howSumRec(target_num, listt, {})

You could still improve on this, if needed, as this does not take advantage of the fact that the order in which you add terms is not important. So you could make sure that a recursive call never looks at terms that are positioned earlier in the list than the last term that was added:

def howSumRec(target_num, listt, i, memo):
    if target_num in memo: 
        return memo[target_num]
    if target_num == 0:
        return []
    if target_num < 0: 
        return None
    for j in range(i, len(listt)):
        num = listt[j]
        remainder = target_num - num
        remainder_result = howSumRec(remainder, listt, j, memo)
        if remainder_result is not None:
            memo[target_num]= *remainder_result, num
            return memo[target_num]
    memo[target_num] = None
    return None

def howSum(target_num, listt):
    return howSumRec(target_num, listt, 0, {})

It is important that with this version, listt is really a list, and not a set, so call it as:

print(howSum(7, [2, 3]))
print(howSum(7, [5, 3, 4, 7]))
print(howSum(7, [2, 4]))
print(howSum(8, [2, 3, 5]))
print(howSum(300, [7, 14]))