所有可能的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  vector<int> path;
  vector<vector<int>> ans;
  int n;
  vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    n = graph.size();
    path.push_back(0);
    dfs(0, graph);
    return ans;
  }
  void dfs(int u, vector<vector<int>>& g) {
    if (u == n - 1) {
      ans.push_back(path);
      return;
    }
    for (int i = 0; i < g[u].size(); i++) {
      path.push_back(g[u][i]);
      dfs(g[u][i], g);
      path.pop_back();
    }
  }
};