# 797. All Paths From Source to Target

Given a directed, acyclic graph of `N` nodes.  Find all possible paths from node `0` to node `N-1`, and return them in any order.

The graph is given as follows:  the nodes are 0, 1, …, graph.length - 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.

``````Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
``````

Note:

• The number of nodes in the graph will be in the range `[2, 15]`.
• You can print different paths in any order, but you should keep the order of nodes inside one path.

``````class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> res;
helper(graph, 0, {}, res);
return res;
}
void helper(vector<vector<int>>& graph, int cur, vector<int> path, vector<vector<int>>& res) {
path.push_back(cur);
if (cur == graph.size() - 1) res.push_back(path);
else for (int neigh : graph[cur]) helper(graph, neigh, path, res);
}
};
``````

``````class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
return helper(graph, 0);
}
vector<vector<int>> helper(vector<vector<int>>& graph, int cur) {
if (cur == graph.size() - 1) {
return {{graph.size() - 1}};
}
vector<vector<int>> res;
for (int neigh : graph[cur]) {
for (auto path : helper(graph, neigh)) {
path.insert(path.begin(), cur);
res.push_back(path);
}
}
return res;
}
};
``````

https://leetcode.com/problems/all-paths-from-source-to-target/solution/

https://leetcode.com/problems/all-paths-from-source-to-target/discuss/121135/6-lines-C++-dfs

https://leetcode.com/problems/all-paths-from-source-to-target/discuss/118691/Easy-and-Concise-DFS-Solution-C++-2-line-Python

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation