797. 所有可能的路径
题目描述
输入一张有向无环图，共 n 个节点，编号 0 到 n - 1。graph[i] 列出从节点 i 出发有边直接指向的节点。
找出所有从节点 0 出发、最终到达节点 n - 1 的路径。每条路径用依次经过的节点编号组成的数组表示。
返回所有这样的路径，路径之间的顺序不限。
示例 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]]
数据范围
n == graph.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i，即没有自环。graph[i]中的元素各不相同。- 保证输入的图是有向无环图。
解题思路：回溯（深度优先搜索）
从节点 0 开始深度优先搜索，用 path 记录当前走过的节点。到达 n - 1 时把 path 的拷贝加入答案；否则依次沿每条出边走下去，回来后把节点弹出 path。因为图是无环的，不会在一条路径上重复访问节点，不需要 visited 数组。
为什么正确
进入 dfs(u) 时，path 是一条从 0 到 u 的合法路径，并以 u 结尾。
复杂度分析
时间 O(2^n * n)（路径数最多 2^(n-2) 条），空间 O(n) 的递归栈（不计答案）。
易错点
加入答案时必须拷贝 path，否则之后的 pop 会改掉已保存的路径；到达终点后也要记得返回。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
target = len(graph) - 1
ans = []
path = [0]
def dfs(u):
if u == target:
ans.append(path[:])
return
for v in graph[u]:
path.append(v)
dfs(v)
path.pop()
dfs(0)
return ansclass Solution {
int[][] graph;
int target;
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
this.graph = graph;
target = graph.length - 1;
path.add(0);
dfs(0);
return ans;
}
void dfs(int u) {
if (u == target) {
ans.add(new ArrayList<>(path));
return;
}
for (int v : graph[u]) {
path.add(v);
dfs(v);
path.remove(path.size() - 1);
}
}
}class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
int target = graph.size() - 1;
vector<vector<int>> ans;
vector<int> path = {0};
function<void(int)> dfs = [&](int u) {
if (u == target) {
ans.push_back(path);
return;
}
for (int v : graph[u]) {
path.push_back(v);
dfs(v);
path.pop_back();
}
};
dfs(0);
return ans;
}
};func allPathsSourceTarget(graph [][]int) [][]int {
target := len(graph) - 1
ans := [][]int{}
path := []int{0}
var dfs func(u int)
dfs = func(u int) {
if u == target {
ans = append(ans, append([]int{}, path...))
return
}
for _, v := range graph[u] {
path = append(path, v)
dfs(v)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}var allPathsSourceTarget = function(graph) {
const target = graph.length - 1;
const ans = [];
const path = [0];
const dfs = (u) => {
if (u === target) {
ans.push([...path]);
return;
}
for (const v of graph[u]) {
path.push(v);
dfs(v);
path.pop();
}
};
dfs(0);
return ans;
};function allPathsSourceTarget(graph: number[][]): number[][] {
const target = graph.length - 1;
const ans: number[][] = [];
const path = [0];
const dfs = (u: number): void => {
if (u === target) {
ans.push([...path]);
return;
}
for (const v of graph[u]) {
path.push(v);
dfs(v);
path.pop();
}
};
dfs(0);
return ans;
}其他解法
回溯只维护一条当前路径，额外空间最小；记忆化自底向上拼路径，结构清晰且可复用公共后缀，代价是缓存大量中间路径。
解法 2：记忆化：按节点求全部后缀路径 时间 O(2ⁿ·n)，空间 O(2ⁿ·n)
定义 paths(u) 为从 u 到终点 n - 1 的全部路径。终点的答案是 [[n - 1]]；其他节点的答案是对每个邻居 v，在 paths(v) 的每条路径前面加上 u。图是有向无环图，递归一定结束，用哈希表缓存每个节点的结果，避免重复求解。答案是 paths(0)。
把问题拆成子问题，体现了有向无环图上分治和动态规划的思路，很多节点汇合时可以复用后缀。但要保存各节点的全部路径，内存比回溯大得多，输出本身指数级时并不省时间。
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
target = len(graph) - 1
memo = {}
def paths(u):
if u == target:
return [[target]]
if u in memo:
return memo[u]
res = []
for v in graph[u]:
for p in paths(v):
res.append([u] + p)
memo[u] = res
return res
return paths(0)class Solution {
int[][] graph;
int target;
Map<Integer, List<List<Integer>>> memo = new HashMap<>();
List<List<Integer>> paths(int u) {
if (u == target) {
List<List<Integer>> base = new ArrayList<>();
base.add(new ArrayList<>(List.of(target)));
return base;
}
if (memo.containsKey(u)) return memo.get(u);
List<List<Integer>> res = new ArrayList<>();
for (int v : graph[u]) {
for (List<Integer> p : paths(v)) {
List<Integer> path = new ArrayList<>();
path.add(u);
path.addAll(p);
res.add(path);
}
}
memo.put(u, res);
return res;
}
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
this.graph = graph;
target = graph.length - 1;
return paths(0);
}
}class Solution {
public:
vector<vector<int>> graph;
unordered_map<int, vector<vector<int>>> memo;
int target;
vector<vector<int>> paths(int u) {
if (u == target) return {{target}};
auto it = memo.find(u);
if (it != memo.end()) return it->second;
vector<vector<int>> res;
for (int v : graph[u]) {
for (auto& p : paths(v)) {
vector<int> path = {u};
path.insert(path.end(), p.begin(), p.end());
res.push_back(path);
}
}
memo[u] = res;
return res;
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
this->graph = graph;
target = graph.size() - 1;
return paths(0);
}
};func allPathsSourceTarget(graph [][]int) [][]int {
target := len(graph) - 1
memo := map[int][][]int{}
var paths func(u int) [][]int
paths = func(u int) [][]int {
if u == target {
return [][]int{{target}}
}
if res, ok := memo[u]; ok {
return res
}
res := [][]int{}
for _, v := range graph[u] {
for _, p := range paths(v) {
path := append([]int{u}, p...)
res = append(res, path)
}
}
memo[u] = res
return res
}
return paths(0)
}var allPathsSourceTarget = function(graph) {
const target = graph.length - 1;
const memo = new Map();
const paths = (u) => {
if (u === target) return [[target]];
if (memo.has(u)) return memo.get(u);
const res = [];
for (const v of graph[u]) {
for (const p of paths(v)) res.push([u, ...p]);
}
memo.set(u, res);
return res;
};
return paths(0);
};function allPathsSourceTarget(graph: number[][]): number[][] {
const target = graph.length - 1;
const memo = new Map<number, number[][]>();
const paths = (u: number): number[][] => {
if (u === target) return [[target]];
if (memo.has(u)) return memo.get(u)!;
const res: number[][] = [];
for (const v of graph[u]) {
for (const p of paths(v)) res.push([u, ...p]);
}
memo.set(u, res);
return res;
};
return paths(0);
}