All Paths From Source To Target Problem
Description
LeetCode Problem 797.
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.
The graph is given as follows: graph[i] 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][j]).
Example 1:
1
2
3
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Example 2:
1
2
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
Example 3:
1
2
Input: graph = [[1],[]]
Output: [[0,1]]
Example 4:
1
2
Input: graph = [[1,2,3],[2],[3],[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]
Example 5:
1
2
Input: graph = [[1,3],[2],[3],[]]
Output: [[0,1,2,3],[0,3]]
Constraints:
- n == graph.length
- 2 <= n <= 15
- 0 <= graph[i][j] < n
- graph[i][j] != i (i.e., there will be no self-loops).
- All the elements of graph[i] are unique.
- The input graph is guaranteed to be a DAG.
Sample C++ Code
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 {
public:
vector<vector<int>> ans;
int n;
void dfs(vector<vector<int>>& graph, vector<int>& path) {
int node = path.back();
if (node == n-1)
ans.push_back(path);
for (int i = 0; i < graph[node].size(); i ++) {
path.push_back(graph[node][i]);
dfs(graph, path);
path.pop_back();
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
n = graph.size();
vector<int> path;
path.push_back(0);
dfs(graph, path);
return ans;
}
};