All Paths From Source to Target — Problem & Solution
All Paths From Source to Target solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
All Paths From Source to Target is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph, Backtracking
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a directed acyclic graph of n nodes labelled 0 through n - 1, as an adjacency list where graph[i] lists the nodes reachable in one step from i.
Return every path from node 0 to node n - 1, in the order a depth-first search that follows each adjacency list left to right would find them.
Example 1
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[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]]
Example 3
Input: graph = [[]]
Output: [[0]]
Constraints
1 <= graph.length <= 12The graph is a DAG: every edge goes from a lower index to a higher one, except that node 0 may be a target of nothing.The total output stays small.
Hints for All Paths From Source to Target
Hint 1
Depth-first search from node 0, carrying the path built so far.
Hint 2
When you reach the last node, record a copy of the path — not the live array.
Hint 3
Because the graph is acyclic you never need a visited set; just undo the last step when you return.
How to solve All Paths From Source to Target
DFS from node 0 carrying the current path; record a copy whenever the target is reached and pop on the way back.
Approach
- Start
path = [0]. - At
node, if it is the target, appendlist(path); else for each successor push it, recurse, pop.
Why it works
The graph is acyclic, so every simple path is found without a visited set, and following adjacency lists in order yields the required output order.
Complexity
- Time —
O(2^n · n) in the worst case (number of paths) - Space —
O(n) recursion plus the output
Pitfalls
- Appending the live
pathlist instead of a copy makes every recorded path alias the same object.
Reference solution
Python
def allPathsSourceTarget(graph):
target = len(graph) - 1
out = []
path = [0]
def walk(node):
if node == target:
out.append(list(path))
return
for nxt in graph[node]:
path.append(nxt)
walk(nxt)
path.pop()
walk(0)
return outJava
private static void walkPaths(int[][] graph, int node, List<Integer> path, List<int[]> out) {
if (node == graph.length - 1) {
int[] copy = new int[path.size()];
for (int i = 0; i < path.size(); i++) copy[i] = path.get(i);
out.add(copy);
return;
}
for (int next : graph[node]) {
path.add(next);
walkPaths(graph, next, path, out);
path.remove(path.size() - 1);
}
}
public static int[][] allPathsSourceTarget(int[][] graph) {
List<int[]> out = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(0);
walkPaths(graph, 0, path, out);
return out.toArray(new int[0][]);
}C++
static void walkPaths(vector<vector<int>>& graph, int node, vector<int>& path, vector<vector<int>>& out) {
if (node == (int) graph.size() - 1) {
out.push_back(path);
return;
}
for (int next : graph[node]) {
path.push_back(next);
walkPaths(graph, next, path, out);
path.pop_back();
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> out;
vector<int> path;
path.push_back(0);
walkPaths(graph, 0, path, out);
return out;
}JavaScript
var allPathsSourceTarget = function(graph) {
const target = graph.length - 1;
const out = [];
const path = [0];
const walk = function(node) {
if (node === target) {
out.push(path.slice());
return;
}
for (let i = 0; i < graph[node].length; i++) {
path.push(graph[node][i]);
walk(graph[node][i]);
path.pop();
}
};
walk(0);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)