python dictionary .get() vs element in dictionary giving different results in DP based recursion pro-CodePudding

dictionary get vs in behaving differently in cansum code

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!

When replacing the 4th line with if memo.get(targetSum) the function does not work for the last input, keeps running due to huge time complexity

def canSum(targetSum, numbers, memo=None):
    if memo == None:
        memo = {}

    if memo.get(targetSum,False):
        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 -> Keeps running no output obtained

Can anyone explain the reason why? I am aware of how .get and in work differently, have enclosed related SO threads below:

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

Python Dictionary: "in" vs "get"

CodePudding user response：

The two versions of your code are not equivalent.

In the case where memo[targetSum] exists and is False, the block:

if targetSum in memo:
    return memo[targetSum]

will return False, but

if memo.get(targetSum,False):
    return memo[targetSum]

won't execute the return, as memo.get(targetSum,False) is False. In this case, you will run the loop at the end of the function.