Why adding memo in recursion problem gives wrong result while removing memo gives correct answer?

Question

Q. Write a function "canSum(target_sum, numbers)" that takes in a target_sum and an array of numbers as arguments. The function should return a boolean indicating whether or not it is possible to generate the target_sum using numbers from the array.

You may use an element of the array as many times as needed. You may assume that all numbers are non-negative.
Eg: canSum(7, [1, 2, 5, 3, 7]) --> true
Eg: canSum(7, [2, 4, 9, 6]) --> false

Here is my solution, but it only works when i remove memoization.

    def canSum(target_sum, numbers, memo={}):
        if target_sum in memo:
           return memo[target_sum]
        if target_sum == 0:
            return True
        if target_sum < 0:
            return False

        for num in numbers:
           if canSum(target_sum - num, numbers, memo) == True:
               memo[target_sum] = True # removing this gives expected output.
               return True

        memo[target_sum] = False # removing this gives expected output.
        return False

   if __name__ == "__main__":
      print(canSum(7, [2, 5, 7])) # Output: True
      print(canSum(7, [2, 4])) # Output: True (while it should be false).

After removing memo, now it works correctly. Please help, I cant find why is this happening.

for num in numbers:
    if canSum(target_sum - num, numbers, memo) == True:
        return True

return False
# Now it works fine.

The mutable default parameter `memo={}` is the problem. The empty dictionary is created once, when you create the function, *not* on every call of the function. See ["Least Astonishment" and the Mutable Default Argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument). — timgeb, Dec 10 '21 at 09:32
Because your current "memoisation" doesn't take into account _which numbers were provided_. It just returns the result for whichever list of numbers was provided the first time a given target_sum was used. — jonrsharpe, Dec 10 '21 at 09:33
To tackle the problem with the mutable parameter you could define the function as `def canSum(target_sum, numbers, memo=None):` and in the first line `if memo is None: memo = {}`. — Matthias, Dec 10 '21 at 09:36

BlackShadow334 · Accepted Answer · 2021-12-10T20:21:05.807

I eventually found the answer. In previous code canSum(target_sum, numbers, memo={}, memo was same for all function call.

I mean for canSum(7, [2, 5, 7]) and canSum(7, [2, 4]) memo is same for both.

So, when it calls the function for 2nd time, it checks for the previously-stored key and returns according to it.

  if target_sum in memo:
       return memo[target_sum]

And that's where, all this ghop-chop happens.

Here's my corrected code.

  def canSum(target_sum, numbers):
       memo = {}
       return memoCanSum(target_sum, numbers, memo)


  def memoCanSum(target_sum, numbers, memo):
      if target_sum in memo:
          return memo[target_sum]
      if target_sum == 0:
          return True
      if target_sum < 0:
          return False

      for num in numbers:
          if memoCanSum(target_sum - num, numbers, memo) == True:
              memo[target_sum] = True
              return True

      memo[target_sum] = False
      return False


  if __name__ == "__main__":
      print(canSum(7, [2, 5, 7])) # Output: True
      print(canSum(7, [2, 4])) # Output: False
      print(canSum(9, [2, 4])) # Output: False

Here, another function is created memoCanSum(target_sum, numbers, memo) and called it from canSum(target_sum, numbers). Now every time canSum is called, it will work fine because in every call memo is set to empty.

Why adding memo in recursion problem gives wrong result while removing memo gives correct answer?

1 Answers1