在 Go 中回溯以查找有向无环图中的所有路径，为解切片分配路径时出现问题

Question

我正在尝试在Go中使用Leetcode 747。问题摘要：

给定一个有向无环图 （DAG），其中包含从 0 到 n - 1 的 n 个节点，找到从节点 0 到节点 n - 1 的所有可能的路径，并按任意顺序返回它们。

图给出如下：graph[i]是您可以从节点i访问的所有节点的列表（即，从节点i到节点图[i][j]有一个有向边）。

到目前为止，这是我的解决方案：

func allPathsSourceTarget(graph [][]int) [][]int {

    allSolutions := [][]int{}

    target := len(graph) - 1

    isSolution := func(current int) bool {

        return current == target

    }

    processSolution := func(solution []int) {

        allSolutions = append(allSolutions, solution)

    }

    var backtrack func(currentPath []int)

    backtrack = func(a []int) {

        currentNode := a[len(a)-1]

        if isSolution(currentNode) {

            processSolution(a)

        } else {

            candidates := graph[currentNode]

            for _, c := range candidates {

                a = append(a, c)

                backtrack(a)

                a = a[:len(a)-1]

            }

        }

    }

    backtrack([]int{0})

    return allSolutions

}

它传递7/30输入，但随后在此输入上失败。其预期输出为 。[[4,3,1],[3,2,4],[3],[4],[]][[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

我认为问题在于如何将每个结果附加到切片。如果我每次都记录进来的解决方案，这是预期的，但它似乎会改变已经添加的解决方案。allSolutions

如果我将日志添加到函数中，对于上述输入，这是输出：allSolutions

Solution:

[0 4]

New allSolutions:

[[0 4]]

Solution:

[0 3 4]

New allSolutions:

[[0 3] [0 3 4]]

Solution:

[0 1 3 4]

New allSolutions:

[[0 1] [0 3 4] [0 1 3 4]]

Solution:

[0 1 2 3 4]

New allSolutions:

[[0 1] [0 3 4] [0 1 2 3] [0 1 2 3 4]]

Solution:

[0 1 4]

New allSolutions:

[[0 1] [0 3 4] [0 1 4 3] [0 1 2 3 4] [0 1 4]]

我很想知道为什么会发生这种情况。它是否与从更高范围修改变量有关？

Answer 1

processSolution应该复制其参数。否则，继续改变它传入的切片，从而导致您看到的损坏。backtrack