LeetCode LCR 110. 所有可能的路径

约 5 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
深度优先搜索 广度优先搜索 LCR 回溯 图

题目描述

✅ LCR 110. 所有可能的路径

image-20260929004556808

image-20260929004556809

image-20260929004556810

题意分析

给定有向无环图，返回从节点 0 到节点 n-1 的全部路径，输出顺序不限。邻接表只表示给定方向的边，不能反向行走。

题目要求具体路径，因此到达同一节点的不同前缀都要保留。可以用 DFS 逐条枚举出边，并维护当前从起点走到的位置序列。

解法：DFS 回溯有向无环图路径

核心思路

[!blue]

用共享列表 path 保存当前路径，第一次调用前先放入起点 0。进入 dfs(i) 时，path 恰好是从起点到 i 的完整路径；函数负责枚举从这里继续到目标的全部走法，返回时保持这条路径不变。

若 i == n-1，当前路径已是一个答案，复制后保存并返回。停止的依据是到达指定目标，不需要假定目标一定没有出边，也不能继续走出目标后再把更长路径当成答案。

否则，依次遍历每条出边 i→j：先把 j 加入路径，再调用 dfs(j)，返回后弹出最后一个节点。子调用会把自身继续探索的部分恢复，调用方再撤销这一次选择，下一条出边就仍从相同前缀出发。

路径在探索过程中反复修改，因此保存答案时必须复制。Java 用新的 ArrayList 保存当前元素；Go 将路径元素追加到新切片，使结果不再共享会被后续回溯修改的底层数组。

有向无环保证一条路径不会再次回到已经包含的节点，递归深度不会超过节点数，无需额外判环。不同路径可以经过同一个节点，所以不能用不回退的全局访问标记屏蔽后来的前缀。每条出边都被枚举，每个选择序列只探索一次，得到的正是全部目标路径；提前走到没有出边的非目标节点时，则直接返回，不保存答案。

解题步骤

  1. 初始化空答案列表和只包含起点的当前路径，再调用 dfs(0)。
  2. 当前节点为目标时，保存路径副本并立即返回。
  3. 否则遍历当前节点的每个出边邻居，执行加入邻居、递归、弹出邻居。
  4. 当前节点没有出边或所有分支处理完后返回，路径恢复为进入本次调用时的状态。
  5. 顶层调用结束后返回答案；没有任何路径到达目标时，结果保持为空。

代码实现

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(n2^n)$。DAG 中不同路径前缀本身可能有指数数量，枚举和复制路径需要计入路径长度；搜索还可能进入不能到达目标的分支，不能只按最终成功输出的条数计时。
  • 空间复杂度：当前路径和递归栈的辅助空间为 $O(n)$。结果还需要保存所有输出路径，按实际输出节点总数另外计算。

关键点总结

[!green]

  • 进入递归时路径已经包含当前节点，起点也遵守同一个约定。
  • 选择、递归、撤销保持成对，使不同分支共享存储而不互相污染。
  • 当前路径可复用，已经收集的答案必须有独立副本。
  • 无环限制单条路径深度，全局访问标记却会误删不同前缀形成的其他答案。

易错点总结

[!yellow]

  • 只记录访问过的节点而不记录路径前缀，会把不同答案合并掉。
  • 递归返回后不弹出末项，下一分支会带上前一分支的残留节点。
  • 保存共享列表或切片引用，后续回溯会改动已经收集的结果。
  • 初始路径没有起点，最终每条答案都会少一个节点。
  • 只在无出边节点处收集答案，会把非目标死路算进去；应判断当前编号是否为 n-1。

相似题目

题目 难度 关联与区别
126. 单词接龙 II 困难 同样输出从起点到终点的多条路径，原题只要最短路径，本题DAG中所有路径都要保留。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/99037397
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！