algorithm - 在Go中回溯以找到有向非循环图的所有路径，将路径分配给解决方案 slice 时出现问题(Leetcode 797)

Question

我正在Go中尝试Leetcode 747。问题总结:

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n -1, find all possible paths from node 0 to node n - 1, and return themin any order.

The graph is given as follows: graph[i] is a list of all nodes you canvisit from node i (i.e., there is a directed edge from node i to nodegraph[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 slice 。如果我每次都记录解决方案，那是预期的结果，但是似乎会使已添加的解决方案发生变化。
如果将日志添加到 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会继续对传入的 slice 进行突变，从而导致您看到的损坏。