用递归解决 DFS 问题它是如何工作的？

Question

问题来了

有n个非负整数。我们要适当地添加或减去这些数字，以达到我们的目标数字。例如，要从[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
+1+1+1+1-1 = 3

写出解法函数return在给定数组数、目标数和目标数作为参数的情况下，通过适当的加减法使目标数的方法数

限制

给出的数字数量为2个或更多且20个或更少。
每个数都是1到50之间的自然数。
目标数为1到1000之间的自然数。

I/O 例子

numbers: [1,1,1,1,1]
target: 3
return: 5

方法

                                    1

                                  /   \

                               -1       1

                             /   \     /   \

                           -1     1  -1     1
                           
                           -1     1   1     3

以 DFS 方式发现此方法，检查所有情况，如果数字的组合等于目标数字则进行加法或减法计数。

代码如下：

def solution(numbers, target):
    total = 0
    num_len = len(numbers)

    def dfs(index=0):
        if index < num_len:
            numbers[index] *= 1
            print('positive / index', index, numbers)
            dfs(index + 1)

            numbers[index] *= -1
            print('negative / index', index, numbers)
            dfs(index + 1)

        else:
            if sum(numbers) == target:
                nonlocal total
                total += 1
                print('matched / index', index, numbers)

    dfs()

    return total

但是，我想知道它是如何运行的，控制台日志记录也是如此。

positive / index 0 [1, 1, 1, 1, 1]
positive / index 1 [1, 1, 1, 1, 1]
positive / index 2 [1, 1, 1, 1, 1]
positive / index 3 [1, 1, 1, 1, 1] 
positive / index 4 [1, 1, 1, 1, 1]
negative / index 4 [1, 1, 1, 1, -1]
matched / index 5 [1, 1, 1, 1, -1]
negative / index 3 [1, 1, 1, -1, -1] ### how come this index all of sudden becomes 3? ###
positive / index 4 [1, 1, 1, -1, -1]
                ...

我有点理解索引递归递增直到匹配/索引5 但不太清楚为什么下次它变成 3.

Answer 1

日志记录格式可能会让您感到困惑。在 5 之后，没有更多的递归调用要进行，因此下一个打印行与一个较旧的堆栈框架相关联，该堆栈框架一直在等待其子级在探索下一个递归调用链之前解决。

如果添加缩进，您会更清楚地看到 parent-children 关系：

print("  " * index + 'positive', numbers)

0 1 2 3 4 5     stack depth
===========================
positive [1, 1, 1, 1, 1]
  positive [1, 1, 1, 1, 1]
    positive [1, 1, 1, 1, 1]
      positive [1, 1, 1, 1, 1]
        positive [1, 1, 1, 1, 1]
        negative [1, 1, 1, 1, -1]
          matched [1, 1, 1, 1, -1]
      negative [1, 1, 1, -1, -1]  <-- here's the call you asked about
      ... calls continue ...

在这里，您可以看到您的问题所涉及的否定分支在深度 3 中返回并且不是 matched 的子分支。在 matched 调用之后，没有更多的子节点需要探索，堆栈弹出回到父节点，父节点也没有更多的节点需要探索，并弹出回到深度为 2 的父节点，它仍然有它的 negative 要探索的子调用链，它会这样做，产生对深度 3 的第二次调用。

用递归解决 DFS 问题它是如何工作的？

DFS problem solving with recursion how does it work?

python

recursion

depth-first-search