Problem Statement
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. – 0 → 1 → 2 – 0 → 2
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.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i(i.e., there will be no self-loops).- All the elements of
graph[i]are unique. - The input graph is guranteed to be a DAG.
Approach
- Treat the graph as a directed adjacency list.
- Start DFS from node 0 and aim to reach the last node (n − 1).
- Maintain a current path list to track the nodes visited on the current route.
- Whenever we reach the target node, store a copy of the current path in the result.
- For each neighbor of the current node,
- add the neighbor to the path,
- recursively explore it,
- then backtrack by removing the neighbor after returning.
- Return the list of all valid paths.
Dry Run
Input: graph = [[1,2],[3],[3],[]]
Graph Structure (Adjacency List): 0 → [1, 2] 1 → [3] 2 → [3] 3 → []
Initialize:
start = 0
end = 3
allPaths = [ ]
Start DFS: dfs(0, [0])
• curr = 0
• neighbors = [1, 2]
Explore neighbor 1:
• path = [0,1]
dfs(1, [0,1])
• curr = 1
• neighbors = [3]
Explore neighbor 3:
• path = [0,1,3]
dfs(3, [0,1,3])
• curr === end → push [0,1,3] into allPaths
Backtrack to curr = 0
Explore neighbor 2:
• path = [0,2]
dfs(2, [0,2])
• curr = 2
• neighbors = [3]
Explore neighbor 3:
• path = [0,2,3]
dfs(3, [0,2,3])
• curr === end → push [0,2,3] into allPaths
All neighbors of 0 explored
Final Answer:
allPaths = [[0,1,3], [0,2,3]]
Output: [[0,1,3],[0,2,3]]
var allPathsSourceTarget = function(graph) {
let start = 0;
let end = graph.length - 1;
let allPaths = [];
let dfs = (curr, path) => {
if(curr === end){
allPaths.push([...path]);
return;
}
for(let neighbor of graph[curr]){
path.push(neighbor)
dfs(neighbor, path);
path.pop();
}
}
dfs(0, [0])
return allPaths;
};
from typing import List
def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
target = len(graph) - 1
res = []
path = []
import java.util.*;
public class Solution {
public List> allPathsSourceTarget(int[][] graph) {
int target = graph.length - 1;
List> res = new ArrayList<>();
LinkedList path = new LinkedList<>();
dfs(0, target, graph, path, res);
return res;
}
private void dfs(int node, int target, int[][] graph, LinkedList path, List> res) {
path.add(node);
if (node == target) {
res.add(new ArrayList<>(path));
} else {
for (int nei : graph[node]) {
dfs(nei, target, graph, path, res);
}
}
path.removeLast();
}
}
def dfs(node):
path.append(node)
if node == target:
res.append(path.copy())
else:
for nei in graph[node]:
dfs(nei)
path.pop()
dfs(0)
return res
import java.util.*;
public class Solution {
public List> allPathsSourceTarget(int[][] graph) {
int target = graph.length - 1;
List> res = new ArrayList<>();
LinkedList path = new LinkedList<>();
dfs(0, target, graph, path, res);
return res;
}
private void dfs(int node, int target, int[][] graph, LinkedList path, List> res) {
path.add(node);
if (node == target) {
res.add(new ArrayList<>(path));
} else {
for (int nei : graph[node]) {
dfs(nei, target, graph, path, res);
}
}
path.removeLast();
}
}
#include <bits/stdc++.h>
using namespace std;
vector> allPathsSourceTarget(vector>& graph) {
int target = graph.size() - 1;
vector> allPaths;
vector path;
function dfs = [&](int node) {
path.push_back(node);
if (node == target) {
allPaths.push_back(path);
} else {
for (int nei : graph[node]) {
dfs(nei);
}
}
path.pop_back();
};
dfs(0);
return allPaths;
}
#include <stdlib.h>
#include <stdio.h>
static int **results = NULL;
static int *resultsCols = NULL;
static int resultsCount = 0;
static int resultsCap = 0;
void add_result(int *path, int len) {
if (resultsCount == resultsCap) {
resultsCap = resultsCap == 0 ? 8 : resultsCap * 2;
results = (int**)realloc(results, resultsCap * sizeof(int*));
resultsCols = (int*)realloc(resultsCols, resultsCap * sizeof(int));
}
int *copy = (int*)malloc(len * sizeof(int));
for (int i = 0; i < len; ++i) copy[i] = path[i];
results[resultsCount] = copy;
resultsCols[resultsCount] = len;
resultsCount++;
}
void dfs_c(int node, int target, int *path, int pathLen, int **graph, int *graphColSize) {
path[pathLen++] = node;
if (node == target) {
add_result(path, pathLen);
} else {
for (int i = 0; i < graphColSize[node]; ++i) {
int nei = graph[node][i];
dfs_c(nei, target, path, pathLen, graph, graphColSize);
}
}
}
int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
// reset globals
results = NULL;
resultsCols = NULL;
resultsCount = 0;
resultsCap = 0;
int target = graphSize - 1;
int *path = (int*)malloc((graphSize + 5) * sizeof(int)); // max depth = graphSize
dfs_c(0, target, path, 0, graph, graphColSize);
free(path);
*returnSize = resultsCount;
*returnColumnSizes = resultsCols;
return results;
}
using System;
using System.Collections.Generic;
public class Solution {
public IList> AllPathsSourceTarget(int[][] graph) {
int target = graph.Length - 1;
var res = new List>();
var path = new List();
void Dfs(int node) {
path.Add(node);
if (node == target) {
res.Add(new List(path));
} else {
foreach (var nei in graph[node]) {
Dfs(nei);
}
}
path.RemoveAt(path.Count - 1);
}
Dfs(0);
return res;
}
}
