All Paths From Source to Target
All Paths From Source to Target is a medium graphs problem solved with the bfs / dfs basics pattern.
The best approach, optimal (dfs with backtracking), runs in O(2^n · n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs over partial paths) up.
Problem
You are given a directed acyclic graph with n nodes labelled 0 to n - 1, as an adjacency list: graph[i] lists every node that has an edge coming from node i.
Return every path that starts at node 0 and ends at node n - 1. Each path is the list of nodes visited in order. The paths may be returned in any order.
Examples
Example 1
- Input
graph = [[1,2,3],[3],[3],[]]- Output
[[0,1,3],[0,2,3],[0,3]]- Why
- Node 0 can go straight to 3, or detour through 1 or through 2 first.
Example 2
- Input
graph = [[2],[2,3],[3],[]]- Output
[[0,2,3]]- Why
- Node 1 has outgoing edges but nothing leads into it from 0, so it never appears.
Example 3
- Input
graph = [[1],[]]- Output
[[0,1]]- Why
- Two nodes and a single edge give exactly one path.
Constraints
n == graph.length,2 <= n <= 150 <= graph[i][j] < nandgraph[i][j] != i- The values in each
graph[i]are distinct. - The graph is a directed acyclic graph (no cycles).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (BFS over partial paths) | O(2^n · n²) | O(2^n · n) |
| Optimal (DFS with backtracking) | O(2^n · n) | O(n) |
1Brute force (BFS over partial paths)
O(2^n · n²)There can be up to 2^(n-2) paths, and every partial path is copied (O(n)) for each of its up to n neighbours.O(2^n · n)The queue can hold an exponential number of partial paths at the same time.Keep a queue of partial paths, each starting at 0. Pop a path, and for every neighbour of its last node, push a copy extended by that neighbour. A path whose last node is n - 1 goes into the answer.
- Push the path [0] into a queue.
- Pop a path. If its last node is n - 1, add it to the result and continue.
- Otherwise, for every neighbour v of the last node, copy the path, append v, and push the copy.
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int target = graph.length - 1;
List<List<Integer>> result = new ArrayList<>();
Queue<List<Integer>> queue = new ArrayDeque<>();
List<Integer> start = new ArrayList<>();
start.add(0);
queue.add(start);
while (!queue.isEmpty()) {
List<Integer> path = queue.poll();
int last = path.get(path.size() - 1);
if (last == target) {
result.add(path);
continue;
}
for (int next : graph[last]) {
List<Integer> extended = new ArrayList<>(path);
extended.add(next);
queue.add(extended);
}
}
return result;
}
}class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
target = len(graph) - 1
result = []
queue = deque([[0]])
while queue:
path = queue.popleft()
last = path[-1]
if last == target:
result.append(path)
continue
for nxt in graph[last]:
queue.append(path + [nxt])
return resultclass Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
int target = graph.size() - 1;
vector<vector<int>> result;
queue<vector<int>> q;
q.push({0});
while (!q.empty()) {
vector<int> path = q.front();
q.pop();
int last = path.back();
if (last == target) {
result.push_back(path);
continue;
}
for (int next : graph[last]) {
vector<int> extended = path;
extended.push_back(next);
q.push(extended);
}
}
return result;
}
};function allPathsSourceTarget(graph) {
const target = graph.length - 1;
const result = [];
const queue = [[0]];
let head = 0;
while (head < queue.length) {
const path = queue[head++];
const last = path[path.length - 1];
if (last === target) {
result.push(path);
continue;
}
for (const next of graph[last]) {
queue.push([...path, next]);
}
}
return result;
}2Optimal (DFS with backtracking)
O(2^n · n)There are at most 2^(n-2) source-to-target paths and copying each costs O(n); every recursive step is on the way to some node of the DAG.O(n)The recursion stack and the shared path hold at most n nodes (output not counted).Walk the DAG depth-first from 0 while keeping a single shared path. Append a node when you step onto it and remove it when you step back. Each time you stand on n - 1, copy the current path into the answer. Partial paths are never copied, only finished ones.
- path = [0]; call dfs(0).
- dfs(u): if u == n - 1, add a copy of path to the result and return.
- For each neighbour v of u: append v, dfs(v), remove the last element.
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(0);
dfs(graph, 0, path, result);
return result;
}
private void dfs(int[][] graph, int u, List<Integer> path, List<List<Integer>> result) {
if (u == graph.length - 1) {
result.add(new ArrayList<>(path));
return;
}
for (int v : graph[u]) {
path.add(v);
dfs(graph, v, path, result);
path.remove(path.size() - 1);
}
}
}class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
result = []
path = [0]
self.dfs(graph, 0, path, result)
return result
def dfs(self, graph: List[List[int]], u: int, path: List[int], result: List[List[int]]) -> None:
if u == len(graph) - 1:
result.append(path[:])
return
for v in graph[u]:
path.append(v)
self.dfs(graph, v, path, result)
path.pop()class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> result;
vector<int> path = {0};
dfs(graph, 0, path, result);
return result;
}
private:
void dfs(vector<vector<int>>& graph, int u, vector<int>& path, vector<vector<int>>& result) {
if (u == (int)graph.size() - 1) {
result.push_back(path);
return;
}
for (int v : graph[u]) {
path.push_back(v);
dfs(graph, v, path, result);
path.pop_back();
}
}
};function allPathsSourceTarget(graph) {
const result = [];
const path = [0];
dfs(graph, 0, path, result);
return result;
}
function dfs(graph, u, path, result) {
if (u === graph.length - 1) {
result.push([...path]);
return;
}
for (const v of graph[u]) {
path.push(v);
dfs(graph, v, path, result);
path.pop();
}
}Edge cases to test
- Only two nodes with a direct edge
- Nodes that cannot be reached from 0 (they never appear in any path)
- Nodes that are reachable but are dead ends that never lead to n - 1
- A dense DAG where the number of paths grows exponentially
Hints
Hint 1
Because there are no cycles, a walk can never revisit a node, so you do not need a visited set.
Hint 2
Grow a path one node at a time. Whenever the last node of the path is n - 1, save a copy of it.
Hint 3
With DFS you can keep one shared path list: add a node before exploring, remove it after (backtracking).
FAQ
What is the best time complexity for All Paths From Source to Target?
Optimal (DFS with backtracking) runs in O(2^n · n) time and O(n) extra space. There are at most 2^(n-2) source-to-target paths and copying each costs O(n); every recursive step is on the way to some node of the DAG.
Which pattern does All Paths From Source to Target use?
It is a graphs problem that uses the bfs / dfs basics pattern. Other problems with the same pattern: BFS - Normal + Level by Level, DFS - Recursive + Iterative, Clone Graph.
Is there a brute force solution for All Paths From Source to Target?
Yes. Brute force (BFS over partial paths) takes O(2^n · n²) time and O(2^n · n) space. Keep a queue of partial paths, each starting at 0.
Which edge cases should I test for All Paths From Source to Target?
Only two nodes with a direct edge; Nodes that cannot be reached from 0 (they never appear in any path); Nodes that are reachable but are dead ends that never lead to n - 1; A dense DAG where the number of paths grows exponentially.