def can_sum(targetSum, numbers, memo={}):
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 can_sum(remainder, numbers, memo):
memo[targetSum] = True
return True
memo[targetSum] = False
return False
print(can_sum(7, [2, 3])) # True
print(can_sum(7, [5, 3, 4, 7])) # True
print(can_sum(7, [2, 4])) # False
print(can_sum(8, [2, 3, 5])) # True
该解决方法通过使用记忆化搜索(memoization)的方式,用一个字典记录每个targetSum对应的结果,避免重复计算。函数首先判断targetSum是否为0或负数,如果是则返回False。然后遍历numbers数组,将targetSum减去当前数得到剩余值remainder,继续调用can_sum函数判断是否能用剩余的数字组成remainder。如果可以,则返回True,并将当前的targetSum值和True存入memo字典;如果不行,则继续尝试下一个数。最后,如果所有数都不能组成targetSum,则返回False,同时将当前targetSum值和False存入memo字典。