时间戳

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

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

问题描述

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

给定一个从 0 到 n - 1 标记的 n 个节点的有向无环图 (DAG)，找到从节点 0 到节点 n - 1 的所有可能路径，并以任意顺序返回它们。

该图如下所示： graph[i] 是您可以从节点 i 访问的所有节点的列表（即，从节点 i 到节点 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]]

我有兴趣知道为什么会这样。它与从更高范围修改变量有关吗？

标签： algorithmgobacktracking

解决方案

processSolution应该复制它的论点。否则，backtrack继续改变它传入的切片，这会导致您看到的损坏。

推荐阅读