对于目标总和问题，递归没有按预期工作

Question

我在python中写了两个不同的递归函数来解决下面的问题。我写的第二个函数运行正常， returns 结果正确；但是我写的第一个函数 returns 结果是错误的。这两个函数之间的唯一区别是基本条件。你能给我解释一下为什么第一个函数 returns 结果是错误的吗？

问题陈述：

You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

我的代码：

# first function: returns the wrong result
def targetsum(nums, crnt, target):
  print(nums,crnt)
  if target==crnt:
    return 1
  if len(nums)==0:
    return 0
  result = (
    targetsum(nums[1:], crnt + nums[0], target)
    + targetsum(nums[1:], crnt - nums[0], target)
  )
  return result

# second function: returns the correct result
def dfs(curr, nums, target):
  print(nums,curr)
  if not nums:
    return (1 if curr == target else 0)         
  res = (
    dfs(curr + nums[0], nums[1:], target)
    + dfs(curr - nums[0], nums[1:], target)
  )
  return res

nums = [1,1,1,1,1] 
target = 3
crnt=0

print(targetsum(nums, crnt, target))   # prints 4

print(dfs(crnt, nums, target))         # prints 5

我期望输出 5，因为有 5 种分配符号的方法可以使 nums 的总和成为目标 3：

    -1 + 1 + 1 + 1 + 1 = 3
    +1 - 1 + 1 + 1 + 1 = 3
    +1 + 1 - 1 + 1 + 1 = 3
    +1 + 1 + 1 - 1 + 1 = 3
    +1 + 1 + 1 + 1 - 1 = 3

第二个函数，dfs，returns5如预期。但是第一个函数，targetsum, returns 4 是错误的。为什么？

Answer 1

递归的基本情况在您的第一个函数中是错误的 targetsum。函数 targetsum returns 1 如果 crnt == target 立即执行， 即使我们还没有到达数组的末尾。但这是错误的：在到达数组末尾之前，你不应该 return 结果。

在您使用 nums=[1,1,1,1,1] 和 target=3 的示例中，第一个递归调用将如下所示：

 1 1 1 1 1   crnt=0
+1 1 1 1 1   crnt=1
+1+1 1 1 1   crnt=2
+1+1+1 1 1   crnt=3
crnt==3==target!! return 1 immediately!!

你能看出逻辑上的错误吗？ crnt 等于 target，是的，但是我们忘了考虑数组中的最后两个数字。我们不应该 return 1 立即；实际上，目标 3 以 +1+1+1 开头的可能性不是 1 而是 2 种：这两种可能性是 +1+1+1+1-1 和 +1+1+1-1+1。但解决这个问题的唯一方法是深入递归。我们还没有达到基本情况。

您的第二个函数 dfs 正确处理基本情况：条件 if not nums: 表示“如果 nums 为空：”。

对于目标总和问题，递归没有按预期工作

Recursion not working as expected for target sum problem

python

recursion

dynamic-programming

recursive-query