Go 中的回溯以查找有向无环图中的所有路径，将路径分配给解决方案切片的问题（Leetcode 797）

Question

我正在尝试 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 them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[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 会继续改变它传入的切片，从而导致您看到的损坏。

Go 中的回溯以查找有向无环图中的所有路径，将路径分配给解决方案切片的问题（Leetcode 797）

Backtracking in Go to find all paths in Directed Acyclic Graph, problem assigning paths to a solution slice (Leetcode 797)

algorithm

backtracking

go