I’m following this tutorial about dynamic programming and I’m struggling to implement memoization in the following problem:

*Write a function called `canSum(targetSum, numbers)`

that returns `True`

only if the numbers in the array can sum to the target sum. All the numbers in the array are positive integers and you can use them more than once for the solution.

Example:

`canSum(7, [2, 4]) -> False`

because you can’t form 7 by adding 2 and 4. *

My brute force solution was the following one:

def canSum(targetSum, numbers): if targetSum == 0: return True if targetSum < 0: return False for n in numbers: remainder = targetSum - n if canSum(remainder, numbers): return True return False print(canSum(7, [2, 3])) # True print(canSum(7, [5, 3, 4, 7])) # True print(canSum(7, [2, 4])) # False print(canSum(8, [2, 3, 5])) # True

Works well, but it’d be faster if we memoized the solutions of the remainders (this is explained at minute 1:28:03 in the video). I did the following with Python, which is exactly what the instructor is doing, but it only returns `True`

and I can’t figure out why…

def canSum(targetSum, numbers, memo={}): 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 canSum(remainder, numbers, memo): memo[targetSum] = True return True memo[targetSum] = False return False print(canSum(7, [2, 3])) print(canSum(7, [5, 3, 4, 7])) print(canSum(7, [2, 4])) print(canSum(8, [2, 3, 5])) # All of them return True

Thanks to the article shared by @Jared Smith I was able to figure it out.

The problem is caused by how python handles default arguments. From the article:

In Python, when passing a mutable value as a default argument in a function, the default argument is mutated anytime that value is mutated.

My `memo`

dictionary was being mutated every call. So I simply changed `memo=None`

and added a check to see if it was the first call of the function:

def canSum(targetSum, numbers, memo=None): if memo == None: memo = {} 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 canSum(remainder, numbers, memo): memo[targetSum] = True return True memo[targetSum] = False return False print(canSum(7, [2, 3])) # True print(canSum(7, [5, 3, 4, 7])) # True print(canSum(7, [2, 4])) # False print(canSum(8, [2, 3, 5])) # True print(canSum(3000, [7, 14])) # False -> Works fast with large inputs!