# 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],,,[]]
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],,,[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
``````

Example 3:

``````1
2
Input: graph = [,[]]
Output: [[0,1]]
``````

Example 4:

``````1
2
Input: graph = [[1,2,3],,,[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]
``````

Example 5:

``````1
2
Input: graph = [[1,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;
}
};
``````