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
Advertisement
Answer
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!