LeetCode LCR 110. 所有可能的路径
目录
题目描述
题意分析
给一张
n个节点的有向无环图，用邻接表graph描述：graph[i]是从节点i出发能一步到达的所有节点。要求返回从节点0到节点n - 1的全部路径，顺序不限。「全部路径」而不是「最短路径」「路径条数」，这一个词就把解法钉死了：必须枚举，而枚举意味着搜索 + 回溯，而不是任何形式的动态规划或 BFS 计数。要输出方案本身，就不能把等价分支合并。
「有向无环」这四个字是本题最大的礼物。无环意味着任何一条从
0出发的路径都不可能重复经过同一个节点，因此不需要visited数组。这与大多数图搜索题不同，是本题的核心识别点：环的存在才是需要访问标记的根本原因，没有环就没有无限递归的风险。「有向」也要留意：
graph[i]里的邻居只表示i → j这一个方向，不能反向走。若误当成无向图，路径会凭空多出来。约束里
n ≤ 15，非常小。这不是巧合——路径总数在最坏情况下是指数级的（完全 DAG 时约 $2^{n-2}$ 条），题目必须把n压到 15 才能保证输出规模可控。看到「返回所有方案」加上「规模极小」，就该确认自己走在回溯这条路上。边界：
n = 1时起点即终点，答案是只含[0]的一条路径；某些节点可能根本到不了n - 1，搜索进去后自然无功而返，不需要特殊处理；题目保证图中没有自环。
解法：深度优先搜索
核心思路
要输出所有路径，本质上就是在解空间树上做一次完整的遍历：从
0出发，每一步可以走向当前节点的任意一个出边邻居，走到n - 1就得到一条完整路径。没有任何剪枝空间——每一条路径都是必须输出的答案，搜索量下界就等于答案规模。那还需要优化什么？需要优化的是路径本身的维护方式。最朴素的写法是每次递归都把当前路径完整复制一份传给下一层，深度为 $d$、路径数为 $P$ 时会多出 $O(P \cdot d^2)$ 的复制开销。改进办法是只维护一条共享的路径数组：进入一层前把节点追加进去，这一层的所有分支探索完毕后再把它弹出来，让数组恢复到进入这一层之前的样子。这就是回溯。
于是不变量可以写得很干净：在
dfs(i)被调用的那一刻，path恰好等于从起点0走到i的完整路径；当dfs(i)返回时，path与调用前完全一致。前半句保证了到达终点时可以直接把path拍下来作为答案，后半句保证了兄弟分支之间互不污染。「加进去 → 递归 → 弹出来」这三步是维持这条不变量的全部代价。递归函数的语义定为：
dfs(i)表示「path已经是0 → … → i的路径，请把从i继续走到n - 1的所有走法都记入答案」。终止条件是
i == n - 1：此时path就是一条完整答案，必须复制一份存入结果集再返回。为什么必须复制：path是共享的可变数组，后续回溯会不断修改它；直接存引用的话，所有答案最终都会指向同一个（且已被改空的）数组。起点的处理有个小细节：
path在第一次调用dfs(0)之前就要先放入0。因为不变量要求「进入dfs(i)时path已经包含i」，起点也不例外。等价的写法是在dfs内部第一行追加、返回前弹出，两种风格选一种保持一致即可，混用必然出错。因为图无环，任何一条路径都不会重复访问节点，所以既不需要
visited，也不需要在终止条件里检查环——递归深度天然被节点数限制住。
解题步骤
- 准备结果集
answer与共享路径path，并把起点0先放进path。为什么起点要在调用前放入：这样才能满足「进入dfs(i)时path的末尾就是i」这条不变量；否则第一条路径会缺少起点。- 定义
dfs(i)，第一行判断i == graph.length - 1。为什么用graph.length - 1而不是传一个n进来：邻接表的长度就是节点数，直接读取避免多传一个参数；判断的是「当前节点是否为终点」，而不是「路径长度是否达到某个值」。- 命中终点时执行
answer.add(new ArrayList<>(path))并return。为什么要新建列表：path会被后续回溯修改，存引用会让所有答案变成同一个对象。为什么要return：终点没有出边（题目的 DAG 里n - 1通常是汇点），即使有出边也不该继续走——题目要的是到达n - 1的路径，走过头就不是答案了。- 否则遍历
graph[i]中的每个邻居j。为什么直接遍历不做任何过滤：无环保证了j不可能已经在path里，所有出边都是合法的下一步。- 对每个
j依次执行「path.add(j)→dfs(j)→ 弹出末尾」。为什么弹出必须在递归之后：递归期间path要保持包含j的状态，只有当以j为下一步的所有路径都探索完毕，才该把它撤销。为什么弹出不能省略：省略后兄弟分支会看到上一个分支残留的节点，path单调增长，输出的路径全是错的。- 递归自然返回，最终返回
answer。为什么不需要额外收尾：不变量保证了每层退出时path都被还原，顶层退出时path只剩起点0，不影响已经复制出去的结果。以
graph = [[1,2],[3],[3],[]]走一遍，n = 4，终点是节点 3。初始
path = [0]，answer = []，调用dfs(0)。
dfs(0)：0 != 3，遍历graph[0] = [1,2]。先取
j = 1：path变成[0,1]，调用dfs(1)。1 != 3，遍历graph[1] = [3]；取j = 3，path变成[0,1,3]，调用dfs(3)。3 == 3命中终点，复制[0,1,3]存入answer并返回。回到dfs(1)的循环体，弹出末尾，path恢复成[0,1]；graph[1]遍历完毕，dfs(1)返回。回到dfs(0)的循环体，弹出末尾，path恢复成[0]——这一步是关键，它让下一个分支从干净的状态出发。再取
j = 2：path变成[0,2]，调用dfs(2)。2 != 3，遍历graph[2] = [3]；取j = 3，path变成[0,2,3]，调用dfs(3)命中终点，复制[0,2,3]存入answer。回溯两层，path恢复成[0]。
graph[0]遍历完毕，dfs(0)返回，最终answer = [[0,1,3],[0,2,3]]，与题目样例一致。若把「弹出末尾」这一步删掉：第一条路径存入后
path停留在[0,1,3]，走第二个分支时会变成[0,1,3,2]，再走到终点得到[0,1,3,2,3]——一条根本不存在的路径。这是本题最典型的崩溃方式。若在终点处存的是
path的引用而非副本：两条答案都会指向同一个数组，等递归全部退出、path被还原成[0]之后，输出的结果会是[[0],[0]]。这是第二典型的错误。再看
n = 1的边界：graph = [[]]，path初始为[0]，dfs(0)第一行判断0 == graph.length - 1 == 0成立，直接把[0]存入答案，返回[[0]]，主逻辑天然覆盖，不需要特判。
代码实现
class Solution {
private List<List<Integer>> answer;
private int[][] graph;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
answer = new ArrayList<>();
this.graph = graph;
List<Integer> path = new ArrayList<>();
// 进入 dfs(i) 时 path 末尾必须是 i，起点也不例外。
path.add(0);
dfs(0, path);
return answer;
}
private void dfs(int i, List<Integer> path) {
if (i == graph.length - 1) {
// path 是共享可变对象，必须复制一份存入结果。
answer.add(new ArrayList<>(path));
return;
}
// 图无环，任何出边都不会走回已在 path 中的节点，无需 visited。
for (int j : graph[i]) {
path.add(j);
dfs(j, path);
// 递归结束后撤销选择，让兄弟分支从干净状态出发。
path.remove(path.size() - 1);
}
}
}
func allPathsSourceTarget(graph [][]int) [][]int {
var path []int
// 进入 dfs(i) 时 path 末尾必须是 i，起点也不例外。
path = append(path, 0)
var answer [][]int
var dfs func(i int)
dfs = func(i int) {
if i == len(graph)-1 {
// path 底层数组会被后续回溯复用，必须复制一份存入结果。
answer = append(answer, append([]int(nil), path...))
return
}
// 图无环，任何出边都不会走回已在 path 中的节点，无需 visited。
for _, j := range graph[i] {
path = append(path, j)
dfs(j)
// 递归结束后撤销选择，让兄弟分支从干净状态出发。
path = path[:len(path)-1]
}
}
dfs(0)
return answer
}
复杂度分析
- 时间复杂度：$O(2^n \cdot n)$。凭什么：最坏情况是完全 DAG（每个节点都指向所有编号更大的节点），从
0到n-1的路径条数约为 $2^{n-2}$，每条路径长度最多 $n$，输出时还要做一次 $O(n)$ 的复制。搜索本身不做任何多余展开，这个上界就是答案规模本身的量级。- 空间复杂度：$O(n)$（不计返回值）。凭什么：
path最长为 $n$，递归深度最深也是 $n$（无环保证路径不重复节点）。若把结果集算进去则是 $O(2^n \cdot n)$，但那是题目要求的输出本身。
关键点总结
- 「返回所有方案」= 回溯枚举，「返回方案数」= 计数 DP，「返回最短方案」= BFS。看清题目要的是哪一类，比想任何优化都重要——要输出方案就不能合并等价分支，复杂度下界就是答案规模。
- 有向无环是免掉
visited的唯一理由。能主动说出「因为无环所以不必标记访问」，比默默写对更能体现对图搜索的理解；一旦题目允许有环，同一套代码必须补上路径判重。- 回溯的三段式「做选择 → 递归 → 撤销选择」必须成对出现，且撤销一定在递归之后；把它当作肌肉记忆，能避免绝大多数枚举类题目的错误。
- 共享一个
path数组 + 回溯，比每层复制一份路径省掉一个数量级的常数；但收集答案时必须深拷贝，这一对取舍是回溯题的固定搭配。- 让「进入递归时
path已包含当前节点」这条不变量在起点上也成立（提前放入0），可以避免在函数内外两处维护路径导致的错位。- 面试视角：常见追问是「如果图有环怎么办」——回答要点是加
visited并在回溯时同步撤销标记，且此时路径数可能无穷，需要题目额外限制路径长度或不允许重复节点。
易错点总结
- 递归后忘记弹出末尾：
graph = [[1,2],[3],[3],[]]会得到[[0,1,3],[0,1,3,2,3]]，第二条路径根本不存在。- 把
path的引用直接存入结果：同一用例最终输出[[0],[0]]，因为所有答案指向同一个已被还原的数组。- Go 中写成
answer = append(answer, path)：path的底层数组会被后续append复用，两条结果可能互相覆盖，graph = [[1,2],[3],[3],[]]输出的两条路径内容会变得不可预测。- 弹出写在递归之前：
graph = [[1],[2],[]]中dfs(1)执行时path已经不含 1，得到的路径缺节点，输出[[0,2]]而不是[[0,1,2]]。- 起点忘记放入
path：graph = [[1],[]]输出[[1]]而不是[[0,1]]，所有路径统一少了首节点。- 起点既在外面放入、又在
dfs内部第一行再放一次：graph = [[1],[]]输出[[0,0,1]]，节点被重复计入。- 终止条件写成
graph[i].length == 0：graph = [[1,2],[],[3],[]]中节点 1 是死胡同但不是终点，会被误当成答案输出[0,1]。- 命中终点后不
return而继续遍历出边：若终点恰好有出边，路径会越过终点继续延伸，输出比n - 1更长的非法路径。- 误加
visited并在回溯时忘记撤销标记：graph = [[1,2],[3],[3],[]]中节点 3 被第一条路径标记后无法再访问，第二条路径[0,2,3]直接丢失，输出只剩一条。- 把邻接表当成无向图，反向也走一遍：
graph = [[1],[2],[]]会在 1 处走回 0，出现无限递归直至栈溢出。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 797. 所有可能的路径 | 中等 | 与本题同题，可直接套用同一份代码 |
| 113. 路径总和 II | 中等 | 树上的路径枚举，需在回溯的同时维护路径和，且终点是叶子而非固定节点 |
| 257. 二叉树的所有路径 | 简单 | 输出的是字符串而非列表，回溯时要处理分隔符的拼接与撤销 |
| 78. 子集 | 中等 | 解空间树的每个节点都要收集答案，而非只在叶子处收集 |
| 46. 全排列 | 中等 | 需要 visited 标记已用元素，且标记必须与路径同步撤销 |
| 39. 组合总和 | 中等 | 元素可重复选取，靠传起始下标而非访问标记来避免重复组合 |
| 1345. 跳跃游戏 IV | 困难 | 同为隐式图，但求最短步数而非全部路径，因此必须换成 BFS 并做访问标记 |