# LeetCode 797 All Paths From Source to Target 回溯()-其他

## LeetCode 797 All Paths From Source to Target 回溯()

Given a directed acyclic graph (DAG) of n nodes labeled from to , find all possible paths from node to node and return them in any order.

``0``
``n - 1``
``0``
``n - 1``

The graph is given as follows: is a list of all nodes you can visit from node \(i\) (i.e., there is a directed edge from node \(i\) to node ).

``graph[i]``
``graph[i][j]``

### Solution

``````class Solution {
private:

vector<vector<int>> ans;

void dfs(int from, int tgt, vector<vector<int>> graph, vector<int>& path, vector<vector<int>>& ans){
path.push_back(from);
if(from==tgt){
ans.push_back(path); return;
}
for(auto to: graph[from]){
dfs(to, tgt, graph, path, ans);
path.pop_back();
}

}

public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
int sz = graph.size();
vector<int> path;

dfs(0, sz-1, graph, path, ans);
return ans;
}
};
``````
————————

Given a directed acyclic graph (DAG) of n nodes labeled from to , find all possible paths from node to node and return them in any order.

``0``
``n - 1``
``0``
``n - 1``

The graph is given as follows: is a list of all nodes you can visit from node \(i\) (i.e., there is a directed edge from node \(i\) to node ).

``graph[i]``
``graph[i][j]``

### Solution

``````class Solution {
private:

vector<vector<int>> ans;

void dfs(int from, int tgt, vector<vector<int>> graph, vector<int>& path, vector<vector<int>>& ans){
path.push_back(from);
if(from==tgt){
ans.push_back(path); return;
}
for(auto to: graph[from]){
dfs(to, tgt, graph, path, ans);
path.pop_back();
}

}

public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
int sz = graph.size();
vector<int> path;

dfs(0, sz-1, graph, path, ans);
return ans;
}
};
``````