I am facing a problem in this memoizing this function in python, its works just fine in javascript

Question

I wrote this code and it was working well before I memoized it? Its supposed to return true if its possible to sum up to the targetSum using the numbers in the array, and false when its not possible

def can_sum(targetSum,numbers,memo={}):
    if targetSum<0:
        return False
    if targetSum in memo:
        return memo[targetSum]
    if targetSum==0:
        return True
    if targetSum<0:
        return False
    for n in numbers:
        remainder = targetSum-n
        if can_sum(remainder,numbers,memo)==True:
            memo[targetSum]=True
            return True
        
    memo[targetSum]=False
    return False


#all of the values below are coming out to be true 
print(can_sum(7,[2,3]))    #true      ------
print(can_sum(7,[7,5,3,4]))#true            |
print(can_sum(7,[2,4]))    #false           |----[Actual Values]
print(can_sum(8,[2,3,5]))  #true            |
print(can_sum(300,[7,14])) #false     ------

Please provide the solution

Does this answer your question? [how are Recursive function calls in Python are able to find keys in an empty dictionary?](https://stackoverflow.com/questions/65202484/how-are-recursive-function-calls-in-python-are-able-to-find-keys-in-an-empty-dic) — user3840170, Feb 12 '21 at 13:38

score 2 · Answer 1 · answered Feb 12 '21 at 13:39

Issue is you're using the same memo for all the runs.

That's because default values are calculated once
This results in subsequent runs using the same memo table
Correct by using memo = None as default so we can compute new table for each run

Revised Code

def can_sum(targetSum,numbers,memo=None):  # change default to None
    if memo is None:                       # This resets memo at beginning of each run
        memo = {}
    if targetSum<0:
        return False
    if targetSum in memo:
        return memo[targetSum]
    if targetSum==0:
        return True
    if targetSum<0:
        return False
    for n in numbers:
        remainder = targetSum-n
        if can_sum(remainder,numbers,memo)==True:
            memo[targetSum]=True
            return True
        
    memo[targetSum]=False
    return False


#all of the values below are coming out to be true 
print(can_sum(7,[2,3]))    #true      ------
print(can_sum(7,[7,5,3,4]))#true            |
print(can_sum(7,[2,4]))    #false           |----[Revised Code Output]
print(can_sum(8,[2,3,5]))  #true            |
print(can_sum(300,[7,14])) #false     ------

thanks darryl. i got it. i also read the python docs for this problem. it just happened because i called the function multiple times — Ramyak Sharma, Feb 12 '21 at 15:33

score 1 · Answer 2 · answered Feb 12 '21 at 13:32

The problem is that all you're memoizing is the target value. Whatever the result of the first can_sum invocation returns will be the memoized result from then on for that target value. For example, you can run the same two lines of code in two separate interpreters, but swapping the order in which they're invoked changes the result for all subsequent calls for a given target value:

>>> can_sum(7, [2, 4])
False
>>> can_sum(7, [7]) # I've seen 7 before! Last time it was False.
False
>>>

>>> can_sum(7, [7])
True
>>> can_sum(7, [2, 4]) # I've seen 7 before! Last time it was True.
True
>>>

You need to memoize not just the target value, but the values used to sum up to the target value. However, it doesn't make sense to memoize lists of integers, since the order of the integers shouldn't matter. Sets would be more appropriate.

thanks for finding the bug. now, I have replaced the default value of memo to None and kept a condition that if the memo value is none, then it makes memo an empty list otherwise continues with the code. thanks to you and DarrylG — Ramyak Sharma, Feb 12 '21 at 15:28

user2390182 · Answer 3 · 2021-02-12T13:43:59.767

You will have to memoize all parameters, just because a particular targetSum worked for some numbers doesn't mean it will work for others. I would recommend to use the functoools.lru_cache decorator to handle that. However, function parameters must be hashable, hence the extra wrapper to tuplify the list:

from functools import lru_cache

def can_sum(targetSum, numbers):
    return _memo_can_sum(targetSum, tuple(numbers))

@lru_cache(None)
def _memo_can_sum(targetSum, numbers):
    if targetSum <= 0:
        return targetSum == 0        
    return any(_memo_can_sum(targetSum-n, numbers) for n in numbers)

Even for a custom memo implementation, you will have a hard time with memoizing for a list parameter.

I am facing a problem in this memoizing this function in python, its works just fine in javascript

3 Answers3