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
You saving mechanism have bug.
When you call function first time:
print(canSum(7, [2, 3]))
This call will return true and it will create key in dictionary with value true( 7 : true).
This is the reason why it doesnt work
Now we will check 3rd call:
print(canSum(7, [2, 4]))
First thing your function is doing is checking if number 7 is in dictionary:
if targetSum in memo:
return memo[targetSum]
And because from 1st call you alredy have number 7 in dictionary , it will search it and return its value - and from 1st call , value for number 7 is True
This is dictionary before and after first call.
{} # before first call
{1: False, 3: True, 5: True, 7: True} # after first call
After first call , this dictionary will return True for every time you call function with number 7.
And because Python share default argument (it is explained in comment by Jared Smith), every call will return True for number 7
How to fix this ? You must save both targetSum and nums into dictionary and test for both values.
There are two ways to do this:
1st way: Encapsulate targetSum and nums into tuple and use that tuple as key.
This is how will that dict will look
{
(7, (2, 3)) : True,
(7, (5, 3, 4, 7)) : True,
(7, (2, 4)) : False
}
This is implementation of this:
keyTuple = (targetSum, tuple(numbers))
if keyTuple in memo:
return memo[keyTuple]
if targetSum == 0:
return True
if targetSum < 0:
return False
for n in numbers:
remainder = targetSum - n
if canSum(remainder, numbers, memo):
memo[keyTuple] = True
return True
memo[keyTuple] = False
return False
You must also convert list into tuple , because python doesnt allow lists as keys for dictionaries.
Second way is use dictionary of dictionaries. Something like this.
{
7: {
(2,3): True,
(5, 3, 4, 7): True
(2,4): False
}
}
This is implementation :
def canSum(targetSum, numbers, memo={}):
numbersTuple = tuple(numbers)
if targetSum in memo:
targetDict = memo[targetSum]
if numbersTuple in targetDict:
return targetDict[numbersTuple]
else:
memo[targetSum] = {}
if targetSum == 0:
return True
if targetSum < 0:
return False
for n in numbers:
remainder = targetSum - n
if canSum(remainder, numbers, memo):
targetDict = memo[targetSum]
targetDict[numbersTuple] = True
return True
targetDict = memo[targetSum]
targetDict[numbersTuple] = False
return False
If you dont understand something , write comment for me :)
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments