target sum for given array

Question

Write a function canSum(targetSum, numbers) that takes in a targetSum and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the targetSum using numbers from the array.

Dynamic progran

You may use an element of the array as many times as needed.

You may assume that all input numbers are nonnegative.

code:

def canSum(targetsum,numbers,memo={}):

    if targetsum in  memo:
        return memo[targetsum]

    if targetsum==0:
        return True

    if targetsum<0:
        return False

    for num in numbers:

        remainder=targetsum-num
        if (canSum(remainder,numbers,memo)==True):
            memo[targetsum]=True
            return True
            
    memo[targetsum]=True
    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]))

print(canSum(300,[7,14]))

if i call these functions they all printing true only

but actual output is

true

true

false

true 

false

plz help me to slove this

Answer 1

This is a typical mistake, see "Least Astonishment" and the Mutable Default Argument. Outline: do not use mutable default arguments. Your fixed version could look like this (+ I refactored a bit):

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

    if targetsum in memo:
        return memo[targetsum]

    if targetsum < 0:
        return False

    if targetsum == 0:
        return True

    for num in numbers:
        remainder = targetsum - num
        res = memo[targetsum] = canSum(remainder, numbers, memo)
        if res:
            return res

    return memo[targetsum]


print(canSum(7, [2, 3]))

print(canSum(7, [5, 3, 4, 7]))

print(canSum(7, [2, 4]))

print(canSum(8, [2, 3, 5]))

print(canSum(300, [7, 14]))

Output:

True
True
False
True
False