LeetCode 797. 所有可能的路径

2022-06-25 HGNULB 约 8 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 797. 所有可能的路径

题意分析

输入是一个用邻接表描述的有向无环图，节点编号 0 到 n - 1，graph[i] 列出从 i 出发一步能到的节点。要把从 0 到 n - 1 的所有路径全部列出来。

要的是「全部路径」，既不是最短路也不是路径条数。这决定了输出规模本身就可能是指数级的，任何解法都必须真的把每条路径走一遍，谈不上「优化掉」。

无环是最重要的约束信号：不存在绕圈导致无限递归的可能，因此不需要任何访问标记，同一节点也不会在一条路径上出现两次。

数据规模刻意压得很小，n 只有 2 到 15，路径条数上限在 $2^{n-2}$ 量级，这本身就是在提示「就是要你枚举」。边界上要注意 n 可以等于 2，此时若 0 直接连到 1，答案就是单条 [0, 1]。

解法：DFS 回溯构造全部路径

核心思路

先排除一个方向：既然输出规模已经是指数级，就不存在多项式算法，问题的重点从「怎么更快」变成「怎么不重不漏地把每条路径生成出来」。

若真按「先枚举所有节点序列，再逐个验证是不是合法路径」去做，验证工作量远大于路径本身的数量，浪费在了海量非法序列上。

观察路径的结构：从 0 到终点的每条路径都能拆成「一段已经确定的前缀」加上「从当前节点继续走出去的一条子路径」。这个自相似结构正好对应递归 —— 进入某个节点时把它记进路径，退出时删掉，一个共享的 path 数组就能依次呈现出所有路径，不必为每条分支各复制一份。

递归要维持的不变量是「进出对称」：调用 dfs(node) 的那一刻，path 恰好是从 0 走到 node 的一条完整路径且末元素就是 node；dfs(node) 返回之后，path 必须恢复成调用前的样子。前半句保证命中终点时能直接把 path 抄下来，后半句保证兄弟分支之间互不污染。

解题步骤

准备结果集 res 和共享路径 path，先把起点 0 放进 path，然后从节点 0 开始递归。起点在递归外放入，是为了让不变量在第一次调用时就成立。

进入 dfs(node) 后先判断 node 是否为 graph.length - 1。是就把 path 的一份副本加进 res 并返回 —— 必须复制，因为 path 稍后会被回溯改写。

不是终点就遍历 graph[node] 的每个邻居 next：先 path.add(next)，再递归 dfs(next)。顺序不能反，进入递归时路径末尾必须已经是当前节点，否则不变量不成立。

递归返回后立刻 path.remove(path.size() - 1)，把刚加的节点撤掉。这一步是回溯的本体：它让 path 回到进入这一层时的状态，下一个兄弟邻居才能在正确的前缀上继续。

全程不需要 visited。图无环保证了任何一条从 0 出发的路径都不会重复经过同一节点，加了标记反而会误杀合法路径。

以 graph = [[4, 3, 1], [3, 2], [3], [4], []] 走一遍（n = 5，终点是 4）：

初始 path = [0]，进入 dfs(0)。0 不是终点，按邻接表顺序依次尝试 4、3、1。

邻居 4：path 变成 [0, 4]，进入 dfs(4) 命中终点，记录副本 [0, 4]。返回后弹出 4，path 回到 [0]。

邻居 3：path 变成 [0, 3]，dfs(3) 的唯一邻居是 4，path 变成 [0, 3, 4] 命中终点，记录 [0, 3, 4]。逐层弹出，path 回到 [0]。

邻居 1：path 变成 [0, 1]，dfs(1) 有邻居 3 和 2。先走 3，path 变成 [0, 1, 3]，再走到 4 得 [0, 1, 3, 4]，记录；弹回 [0, 1]。再走 2，path 变成 [0, 1, 2]，dfs(2) 走到 3 得 [0, 1, 2, 3]，再走到 4 得 [0, 1, 2, 3, 4]，记录；逐层弹回，path 最终回到 [0]。

递归结束，res = [[0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4]]。注意每次记录后 path 都被完整还原，四条路径的公共前缀 [0] 被复用了三次，这正是回溯省下复制开销的地方。

代码实现

class Solution {
    // 所有路径都可视作“当前路径前缀 + 后续分支”，天然适合回溯生成。
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(0, graph, path, res);
        return res;
    }

    private void dfs(
            int node,
            int[][] graph,
            List<Integer> path,
            List<List<Integer>> res
    ) {
        if (node == graph.length - 1) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int next : graph[node]) {
            path.add(next);
            dfs(next, graph, path, res);
            path.remove(path.size() - 1);
        }
    }
}

func allPathsSourceTarget(graph [][]int) [][]int {
    // 所有路径都可视作“当前路径前缀 + 后续分支”，天然适合回溯生成。
    res := make([][]int, 0)
    path := []int{0}

    var dfs func(node int)
    dfs = func(node int) {
        if node == len(graph)-1 {
            copyPath := make([]int, len(path))
            copy(copyPath, path)
            res = append(res, copyPath)
            return
        }

        for _, next := range graph[node] {
            path = append(path, next)
            dfs(next)
            path = path[:len(path)-1]
        }
    }

    dfs(0)
    return res
}

复杂度分析

时间复杂度：$O(2^n \cdot n)$，最坏情况下（每个节点都连向所有编号更大的节点）路径条数是 $2^{n-2}$ 量级，每条路径长度最多 n，且命中终点时要复制一次 path。这个上界由输出规模决定，无法再降。

空间复杂度：$O(n)$，不计返回值本身。递归深度不超过节点数，path 长度同理，两者都是线性的。

关键点总结

先判断输出规模再谈复杂度。当答案本身就是指数级时，目标应该从「降复杂度」切换到「零浪费地枚举」，别把力气花在不可能的优化上。

回溯的本质是「用一份共享状态依次表示所有候选」。加入与撤销必须严格配对，这条进出对称的约定一旦立住，兄弟分支互不干扰就是自然结果。

记录答案时必须深拷贝。共享状态在下一步就会被改写，直接把引用塞进结果集是回溯题里最高频的错误，没有之一。

是否需要 visited 取决于图有没有环，而不是取决于「这是不是图题」。本题无环所以不需要；一旦有环，标记还必须配合撤销，否则会误杀合法路径。

面试视角：主动说出「因为是 DAG 所以不用 visited」比直接写一个 visited 更能体现你读懂了约束；面试官常会追问「如果图里有环、要求路径不重复经过节点怎么办」，答案是加上标记并在回溯时撤销。

面试视角：另一条值得提的追问是「只要路径条数怎么办」。那时就不必真的构造路径，可以在 DAG 上做记忆化，f(u) 表示从 u 到终点的路径数，复杂度降到 $O(V + E)$。

易错点总结

错误写法：Java 里写 res.add(path) 而不是 res.add(new ArrayList<>(path))。path 是全程共享的同一个对象，回溯会把它一路清空，最终 res 里所有元素都指向同一个只剩 [0] 的列表。

错误写法：Go 里写 res = append(res, path)。切片只是底层数组的视图，后续的 append 与截断会复用同一块内存，已经存进 res 的路径会被悄悄改写；必须先 make 一个等长切片再 copy。

错误写法：递归返回后忘记弹出末尾元素。用 graph = [[1, 2], [3], [3], []] 试：走完 0 → 1 → 3 后 path 还留着 [0, 1, 3]，接着尝试邻居 2 会拼成 [0, 1, 3, 2, 3]，既不是合法路径，节点 3 还出现了两次。

错误写法：把 path.add(next) 挪到递归调用之后。进入下一层时路径末尾还不是当前节点，命中终点时抄下来的路径少了最后一个节点，[0, 4] 会被记成 [0]。

错误写法：起点在递归外放入 path 一次，进入 dfs 后又把 node 放一次。每条路径开头都会多一个 0，结果变成 [0, 0, 4] 这类形状。

错误写法：加一个 visited 数组但只标记不撤销。用 graph = [[4, 3, 1], [3, 2], [3], [4], []] 试：节点 4 在第一条路径 [0, 4] 里被永久标记，后面三条路径全都走不到终点，res 只剩一条。

错误写法：终点判断写成「当前节点没有出边」。用 graph = [[1, 2], [], [3], []] 试：节点 1 同样没有出边，会被误当成终点记下 [0, 1]，而正确答案只有 [0, 2, 3]。终点必须按编号 n - 1 判定。

错误写法：改用 BFS 并在队列里存整条路径，但入队时多个元素共享同一个列表对象。任何一次扩展都会污染其他分支，必须在入队前为每个分支各复制一份，这也是 BFS 在本题不如 DFS 划算的原因。

相似题目

题目	难度	考察点
46. 全排列	中等	选择集是「尚未用过的元素」而非邻接表
79. 单词搜索	中等	网格可走回头路，必须配 `visited` 且回溯时撤销
113. 路径总和 II	中等	树上回溯，终点由「叶子且剩余和为 0」共同决定
257. 二叉树的所有路径	简单	输出是字符串，回溯时要撤销的是拼接长度
841. 钥匙和房间	中等	同样从 0 出发遍历有向图，但只判可达性
LCR 110. 所有可能的路径	中等	与本题完全同构，可直接套用同一份回溯代码