为什么在递归问题中添加备忘录会给出错误的结果，而删除备忘录会给出正确的答案？

Question

问。编写一个函数“canSum(target_sum, numbers)”，它接受一个 target_sum 和一个数字数组作为参数。该函数应该 return 一个布尔值，指示是否可以使用数组中的数字生成 target_sum。

您可以根据需要多次使用数组的元素。你可以假设所有数字都是非负数。
例如：canSum(7, [1, 2, 5, 3, 7]) --> true
例如：canSum(7, [2, 4, 9, 6]) --> false

这是我的解决方案，但它只在我删除记忆时有效。

    def canSum(target_sum, numbers, memo={}):
        if target_sum in memo:
           return memo[target_sum]
        if target_sum == 0:
            return True
        if target_sum < 0:
            return False

        for num in numbers:
           if canSum(target_sum - num, numbers, memo) == True:
               memo[target_sum] = True # removing this gives expected output.
               return True

        memo[target_sum] = False # removing this gives expected output.
        return False

   if __name__ == "__main__":
      print(canSum(7, [2, 5, 7])) # Output: True
      print(canSum(7, [2, 4])) # Output: True (while it should be false).

After removing memo, now it works correctly. Please help, I cant find why is this happening.

for num in numbers:
    if canSum(target_sum - num, numbers, memo) == True:
        return True

return False
# Now it works fine.

Answer 1

我终于找到了答案。在之前的代码 canSum(target_sum, numbers, memo={} 中，memo 与 所有函数调用相同。

我的意思是 canSum(7, [2, 5, 7]) 和 canSum(7, [2, 4]) memo 两者相同。

因此，当它第二次调用该函数时，它会检查先前存储的密钥并根据它returns。

  if target_sum in memo:
       return memo[target_sum]

所有这些 ghop-chop 就是在这里发生的。

这是我更正后的代码。

  def canSum(target_sum, numbers):
       memo = {}
       return memoCanSum(target_sum, numbers, memo)


  def memoCanSum(target_sum, numbers, memo):
      if target_sum in memo:
          return memo[target_sum]
      if target_sum == 0:
          return True
      if target_sum < 0:
          return False

      for num in numbers:
          if memoCanSum(target_sum - num, numbers, memo) == True:
              memo[target_sum] = True
              return True

      memo[target_sum] = False
      return False


  if __name__ == "__main__":
      print(canSum(7, [2, 5, 7])) # Output: True
      print(canSum(7, [2, 4])) # Output: False
      print(canSum(9, [2, 4])) # Output: False

这里，创建了另一个函数 memoCanSum(target_sum, numbers, memo) 并从 canSum(target_sum, numbers) 调用它。现在每次调用 canSum 时，它都会正常工作，因为在每次调用中 memo 都设置为空。

为什么在递归问题中添加备忘录会给出错误的结果，而删除备忘录会给出正确的答案？

Why adding memo in recursion problem gives wrong result while removing memo gives correct answer?

python

dynamic-programming

python-3.x