3_cansum.py

# Return a boolean indicating if the targetsum can be generated by the numbers 
# in the array numbers. Assume all numbers in array are positive and you can 
# reuse the numbers as many times as you wish.

# let n = len(numbers) and m = targetsum
# O(n^m) in time and O(m) in space before memoisation. In general, time will be exponential 
#   --> (branching factor) ^ (height of tree).
# O(n*m) in time and O(m) in space after memoisation


def cansum(targetsum, numbers, memo = None):
    if memo is None: memo = {} # don't use mutables in function definition for python!!
    if targetsum == 0: return True
    if targetsum < 0: return False
    if targetsum in memo: return memo[targetsum]
    
    for num in numbers:
        remainder = targetsum - num
        if cansum(remainder, numbers, memo) == True:
            memo[targetsum] = True
            return True
    
    memo[targetsum] = False
    return False

print(cansum(7,[5,3,4]))
print(cansum(300,[7,14]))