Function that returns a boolean if targetSum can be achieved by adding the numbers present in the numbers array

Question

Code:-

def canSum(targetSum, numbers, d={}):
    if targetSum in d.keys():
        return d[targetSum]
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False
    for each in numbers:
        rem = targetSum - each
        if canSum(rem, numbers, d):
            d[targetSum] = True
            return True
    d[targetSum] = False
    return False

MY ISSUE-
When I run the above code for the testcase - print(canSum(7, [2, 4])), it return false(which is correct). But when I run the same code for the two testcases that are - print(canSum(7, [3, 5, 4])) and print(canSum(7, [2, 4])), it returns true for both!(which is wrong).

I don't know what is happening. Is there something wrong with the code? Help me out.

Answer 1

The problem is with the mutable default argument for d.

Mutable defaults like [] & {} are associated with the function - not the particular invocation of that function. So it carries state over from one invocation to another. That's why your code fails if you run it more than once. Simply put, d is not empty the second time.

You don't even need the d={}. Your code works fine if you remove that.

def canSum(targetSum, numbers, d):
    if targetSum in d.keys():
        return d[targetSum]
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False
    for each in numbers:
        rem = targetSum - each
        if canSum(rem, numbers, d):
            d[targetSum] = True
            return True
    d[targetSum] = False
    return False

print(canSum(7, [2, 4], {}))
print(canSum(7, [3,5,4], {}))

Output:

False
True

If you must keep the signature of canSum as-is, consider defining a wrapper that puts the d={} into the invocation of the recursive function.

Read more: "Least Astonishment" and the Mutable Default Argument