# 797. All Paths From Source to Target

## Description

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:

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:

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]]


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.

## Solutions

Since there is no ring in the graph, you can simply use DFS or BFS to traverse it.

• class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int n = graph.length;
Queue<List<Integer>> queue = new ArrayDeque<>();
queue.offer(Arrays.asList(0));
List<List<Integer>> ans = new ArrayList<>();
while (!queue.isEmpty()) {
List<Integer> path = queue.poll();
int u = path.get(path.size() - 1);
if (u == n - 1) {
continue;
}
for (int v : graph[u]) {
List<Integer> next = new ArrayList<>(path);
queue.offer(next);
}
}
return ans;
}
}


• class Solution {
public:
vector<vector<int>> graph;
vector<vector<int>> ans;

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
this->graph = graph;
vector<int> path;
path.push_back(0);
dfs(0, path);
return ans;
}

void dfs(int i, vector<int> path) {
if (i == graph.size() - 1) {
ans.push_back(path);
return;
}
for (int j : graph[i]) {
path.push_back(j);
dfs(j, path);
path.pop_back();
}
}
};

• class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
q = deque([[0]])
ans = []
while q:
path = q.popleft()
u = path[-1]
if u == n - 1:
ans.append(path)
continue
for v in graph[u]:
q.append(path + [v])
return ans


• func allPathsSourceTarget(graph [][]int) [][]int {
var path []int
path = append(path, 0)
var ans [][]int

var dfs func(i int)
dfs = func(i int) {
if i == len(graph)-1 {
ans = append(ans, append([]int(nil), path...))
return
}
for _, j := range graph[i] {
path = append(path, j)
dfs(j)
path = path[:len(path)-1]
}
}

dfs(0)
return ans
}

• /**
* @param {number[][]} graph
* @return {number[][]}
*/
var allPathsSourceTarget = function (graph) {
const ans = [];
const t = [0];

const dfs = t => {
const cur = t[t.length - 1];
if (cur == graph.length - 1) {
ans.push([...t]);
return;
}
for (const v of graph[cur]) {
t.push(v);
dfs(t);
t.pop();
}
};

dfs(t);
return ans;
};


• impl Solution {
fn dfs(i: usize, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, graph: &Vec<Vec<i32>>) {
path.push(i as i32);
if i == graph.len() - 1 {
res.push(path.clone());
}
for j in graph[i].iter() {
Self::dfs(*j as usize, path, res, graph);
}
path.pop();
}

pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut res = Vec::new();
Self::dfs(0, &mut vec![], &mut res, &graph);
res
}
}


• function allPathsSourceTarget(graph: number[][]): number[][] {
const ans: number[][] = [];

const dfs = (path: number[]) => {
const curr = path.at(-1)!;
if (curr === graph.length - 1) {
ans.push([...path]);
return;
}

for (const v of graph[curr]) {
path.push(v);
dfs(path);
path.pop();
}
};

dfs([0]);

return ans;
}