题目描述
这是 LeetCode 上的 797. 所有可能的路径 ，难度为 中等。
Tag : 「回溯算法」、「DFS」
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。
示例 1：
输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]] 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3 复制代码
示例 2：
输入：graph = [[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]] 复制代码
示例 3：
输入：graph = [[1],[]] 输出：[[0,1]] 复制代码
示例 4：
输入：graph = [[1,2,3],[2],[3],[]] 输出：[[0,1,2,3],[0,2,3],[0,3]] 复制代码
示例 5：
输入：graph = [[1,3],[2],[3],[]] 输出：[[0,1,2,3],[0,3]] 复制代码
提示：
- n == graph.length
- 2 <= n <= 15
- 0 <= graph[i][j] < n
- graph[i][j] != i（即，不存在自环）
- graph[i] 中的所有元素 互不相同
- 保证输入为 有向无环图（DAG）
DFS
nn 只有 1515，且要求输出所有方案，因此最直观的解决方案是使用 DFS 进行爆搜。
起始将 00 进行加入当前答案，当 n - 1n−1 被添加到当前答案时，说明找到了一条从 00 到 n - 1n−1 的路径，将当前答案加入结果集。
当我们决策到第 xx 位（非零）时，该位置所能放入的数值由第 x - 1x−1 位已经填入的数所决定，同时由于给定的 graphgraph 为有向无环图（拓扑图），因此按照第 x - 1x−1 位置的值去决策第 xx 位的内容，必然不会决策到已经在当前答案的数值，否则会与 graphgraph 为有向无环图（拓扑图）的先决条件冲突。
换句话说，与一般的爆搜不同的是，我们不再需要 visvis 数组来记录某个点是否已经在当前答案中。
代码：
class Solution { int[][] g; int n; List<List<Integer>> ans = new ArrayList<>(); List<Integer> cur = new ArrayList<>(); public List<List<Integer>> allPathsSourceTarget(int[][] graph) { g = graph; n = g.length; cur.add(0); dfs(0); return ans; } void dfs(int u) { if (u == n - 1) { ans.add(new ArrayList<>(cur)); return ; } for (int next : g[u]) { cur.add(next); dfs(next); cur.remove(cur.size() - 1); } } } 复制代码
- 时间复杂度：共有 nn 个节点，每个节点有选和不选两种决策，总的方案数最多为 2^n2n，对于每个方案最坏情况需要 O(n)O(n) 的复杂度进行拷贝并添加到结果集。整体复杂度为 O(n * 2^n)O(n∗2n)
- 空间复杂度：最多有 2^n2n 种方案，每个方案最多有 nn 个元素。整体复杂度为 O(n * 2^n)O(n∗2n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No797. 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
