LC.P797[所有可能的路径]

方法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    int[][] graph;
    int n;
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.graph = graph;
        this.n = graph.length;
        path.add(0);
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == n - 1) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j : graph[i]) {
            path.add(j);
            dfs(j);
            path.remove(path.size() - 1);
        }
    }
}
  • 时间复杂度：$O(n \times 2^n)$
  • 空间复杂度：$O(n \times 2^n)$