Skip to content
Advertisement

Why does this solution work in Javascript but not in Python? (Dynamic programming)

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!
User contributions licensed under: CC BY-SA
8 People found this is helpful
Advertisement