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

Question

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 1

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.

Answer 2

Just pass memo when you call it recursively

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 , memo ) #pass memo as well
    
    if remainderResult is not None:
        remainderResult.append(num)
        memo[targetSum] = remainderResult
        return memo[targetSum]
    
memo[targetSum] = None
return None

Answer 3

I think you are not passing your answer array, that's why It is not working. Try this code:

hmap = {}
def howSum(targetSum, numbers,ans=[]):
    if targetSum == 0:
        return ans
    if targetSum <0:
        return None
    if targetSum in hmap:
        return hmap[targetSum]
    for len in numbers:
        remainder = targetSum-len
        remainder_result = howSum(remainder,numbers,ans)
        if remainder_result != None:
            hmap[remainder]  = remainder_result
            ans.append(len)
            return ans
    return None