1

So I created a function canSum(m,n) to return a way if its possible to get a sum 'm' by using numbers given in a list 'n' recursively with using memoization in python. Got this implementation from this YouTube video dynamic programming.

In below code the second print is not right

def can_Sum(m,n,memo = {}):
if m in memo:
    return memo[m]
if m == 0:
    return []
if m < 0:
    return None
for i in n:
    #print(i)
    remainder = m - i
    remainder_Result = can_Sum(remainder,n,memo)
    if(remainder_Result != None):
        memo[m] = remainder_Result + [i]
        return memo[m]
return None
print(can_Sum(6,[12,1,33])) #this prints [1,1,1,1,1,1]
print(can_Sum(7,[2,3]))     #this should prints [3,2,2] but it prints [1,1,1,1,1,2]

But if I do it like this everything is fine

def can_Sum(m,n,memo = {}):
if m in memo:
    return memo[m]
if m == 0:
    return []
if m < 0:
    return None
for i in n:
    #print(i)
    remainder = m - i
    remainder_Result = can_Sum(remainder,n,memo)
    if(remainder_Result != None):
        memo[m] = remainder_Result + [i]
        return memo[m]
return None
print(can_Sum(6,[12,1,33]))
print(can_Sum(7,[2,3],memo={})) #now it runs fine

Any idea why this is happening ? Somehow when a new function call is made the dictionary (memo) is not getting passed as empty, its taking the old dictionary so the output is wrong. But why this is happening ? when I gave an empty dictionary as a default argument or did I make a error and this is not how default arguments are passed in functions in python ?

Thank you

Chetan Anand
  • 11
  • 2
  • 2
    Next time, try to make the difference between the two code blocks more clear. Only the last line seems to be different. The problem is that one instance of a dictionary is created and is used as default value for the `memo` parameter. So the first time `can_Sum()` is called without specifying `memo`, the dictionary from the default value is used. Next time you call `can_Sum()` again without specifying `memo`, it will use the exact same dictionary again, which probably is no longer empty. Use `None` instead as `{}` as default parameter and add this line: `memo = {} if memo is None else memo` – gogognome Jan 08 '21 at 14:32

0 Answers0