Why does howSum solution work in Javascript but not in Python? (Dynamic programming)

This is a follow-up to this question asked on Stack Overflow.

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 None. If there are multiple combinations possible, you may return any single one.

My memoized python code for the solution is as follows:

def howSum(targetSum, nums, memo = None):

    if memo is None:
        memo = {}
        
    if targetSum in memo: return memo[targetSum]
    if targetSum < 0: return None
    if targetSum == 0: return []
    
    for num in nums:
        remainder = targetSum - num
        remainderResult = howSum(remainder, nums)
        
        if remainderResult is not None:
            remainderResult.append(num)
            memo[targetSum] = remainderResult
            return memo[targetSum]
        
    memo[targetSum] = None
    return None

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

The algorithm works but not as efficiently for the final test case. In fact, the runtime efficiency is no different than the brute force solution. What’s the problem?

Answer

You don’t seem to pass the memo value to the recursive howSum(remainder, nums) call, so you’re losing the benefit of memoizing there.

Advertisement

Answer