All Paths From Source to Target: Backtracking Through a DAG
Enumerate every path from node 0 to node n-1 in a DAG with DFS backtracking — intuition, JavaScript code, a full walkthrough, and complexity, step by step.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most graph problems ask a yes/no question — is there a path?, is it connected? — and a single traversal with a visited set answers them. All Paths From Source to Target asks something greedier: give me every route from the start to the end, spelled out node by node.
That word every changes the shape of the solution. You can no longer mark a node visited and forget it, because the same node might sit on ten different paths. Instead you walk a route to its end, record it, then rewind one step and try the next branch. That walk-record-rewind rhythm is backtracking, and this problem is one of the cleanest places to learn it.
The one thing that makes exhaustive enumeration safe here: the graph is a DAG (directed acyclic graph). No cycles means no infinite loops, so you never even need a visited set.
The problem
Given a directed acyclic graph of n nodes labeled 0 to n - 1, return all possible paths from node 0 to node n - 1. The graph comes as an adjacency list: graph[i] is the array of nodes you can travel to directly from node i. Paths may be returned in any order.
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Node 0 → 1 or 2
Node 1 → 3
Node 2 → 3
Node 3 → (target, no outgoing edges)This is a diamond: from 0 you can go left through 1 or right through 2, and both roads meet at the target 3. Two distinct paths, both starting at 0 and ending at 3.
Two facts from the statement quietly drive the solution:
- The target is always node
n - 1—graph.length - 1. You know the finish line before you start. - Because it is acyclic, a node can appear on many paths but never twice on the same path, so no cycle-detection machinery is needed.
The brute force baseline
There is no separate "brute force" here in the Two-Sum sense — enumerating all paths is inherently exponential, because the output itself can be exponential in size. What people get wrong is the naive first instinct: copy the whole path array on every recursive call.
function allPathsNaive(graph, node = 0, path = [0]) {
const target = graph.length - 1;
if (node === target) return [path];
const result = [];
for (const next of graph[node]) {
// new array allocated at every edge — wasteful
result.push(...allPathsNaive(graph, next, [...path, next]));
}
return result;
}This is correct, but it allocates a fresh [...path, next] array for every edge it crosses and merges result arrays with spread on the way back up. On a dense DAG that is a lot of garbage. The optimal version keeps one shared path array and mutates it in place — push before recursing, pop after — so memory stays proportional to the current depth, not the whole search tree.
The key insight
Reframe the search as choose, explore, un-choose.
At any node, each outgoing edge is a choice. You commit to a choice by pushing the neighbor onto your current path, then you fully explore everything reachable through it. When that subtree is exhausted, you un-choose by popping the neighbor back off — leaving the path exactly as it was before you tried that branch, ready for the next sibling edge.
The base case is trivial: when the current node equals the target, the path you are holding is a complete answer. Save a copy of it and return. The copy matters — the shared path array keeps mutating as backtracking continues, so storing a reference would leave you with the same array pointer in every slot, all showing the final (empty) state.
This is the backtracking template that powers subsets, permutations, combination sum, and N-Queens. All Paths is that template with the tree structure handed to you directly as a graph.
The optimal solution
This is the exact algorithm the visualizer traces — one shared path, an inner dfs closure, and a copy-on-save at the target.
var allPathsSourceTarget = function(graph) {
let start = 0;
let end = graph.length - 1;
let allPaths = [];
let dfs = (curr, path) => {
if (curr === end) {
allPaths.push([...path]); // save a COPY, not the reference
return;
}
for (let neighbor of graph[curr]) {
path.push(neighbor); // choose
dfs(neighbor, path); // explore
path.pop(); // un-choose (backtrack)
}
};
dfs(0, [0]);
return allPaths;
};Read the three lines inside the loop as a unit. path.push(neighbor) extends the route, dfs(neighbor, path) recurses into that neighbor's subtree, and path.pop() restores the route before the next iteration touches it. Because there are no cycles, this recursion always terminates — every edge points "forward" toward higher-numbered reachable nodes, and the target has no outgoing edges to continue from.
Note there is no visited set anywhere. That is deliberate and correct only because the input is a DAG. Add a visited set out of habit and you would wrongly block legitimate paths that revisit a shared node.
Walkthrough
Tracing graph = [[1,2],[3],[3],[]], target = 3. The path column is the single shared array; watch it grow and shrink.
| Step | Call | curr | Action | path after | allPaths |
|---|---|---|---|---|---|
| 1 | dfs(0) | 0 | not target; neighbors [1,2]; push 1 | [0,1] | [] |
| 2 | dfs(1) | 1 | not target; neighbors [3]; push 3 | [0,1,3] | [] |
| 3 | dfs(3) | 3 | target! copy [0,1,3] | [0,1,3] | [[0,1,3]] |
| 4 | ↩ dfs(1) | 1 | pop 3 (backtrack) | [0,1] | [[0,1,3]] |
| 5 | ↩ dfs(0) | 0 | pop 1 (backtrack) | [0] | [[0,1,3]] |
| 6 | dfs(0) | 0 | push next neighbor 2 | [0,2] | [[0,1,3]] |
| 7 | dfs(2) | 2 | not target; neighbors [3]; push 3 | [0,2,3] | [[0,1,3]] |
| 8 | dfs(3) | 3 | target! copy [0,2,3] | [0,2,3] | [[0,1,3],[0,2,3]] |
| 9 | ↩ dfs(2) | 2 | pop 3 | [0,2] | [[0,1,3],[0,2,3]] |
| 10 | ↩ dfs(0) | 0 | pop 2; loop done | [0] | [[0,1,3],[0,2,3]] |
Step 5 is the heart of backtracking: after fully exploring the 0 → 1 branch, the path shrinks back to [0] so the 0 → 2 branch starts from a clean slate. The same physical array served both paths — the copy at steps 3 and 8 is what froze each answer before the array kept changing.
Complexity
Let n be the number of nodes. The result can be exponentially large, so the bound is unavoidably exponential.
| Metric | Complexity | Why |
|---|---|---|
| Time | O(2ⁿ · n) | Up to 2ⁿ⁻¹ distinct paths in the worst DAG, each up to length n to copy |
| Space (aux) | O(n) | Recursion depth + the single shared path array, both bounded by n |
| Space (with output) | O(2ⁿ · n) | Storing every enumerated path dominates |
The worst case is the DAG where every node i points to every node j > i. From node 0 you can reach n - 1 through any subset of the middle nodes, giving 2ⁿ⁻² paths. No algorithm can beat exponential time when the answer is exponential — you simply cannot print 2ⁿ paths faster than 2ⁿ. The in-place push/pop keeps the auxiliary space linear, which is the part you actually control.
Common mistakes
- Storing the path by reference.
allPaths.push(path)instead ofallPaths.push([...path])pushes the same array pointer every time. After backtracking finishes, every entry shows the final state (often just[0]or[]). Always copy at the target. - Adding a visited set. Correct for cycle-prone graphs, wrong here. A node legitimately appears on multiple paths; blocking re-entry silently drops valid routes. The DAG guarantee is what lets you skip it.
- Forgetting to pop. Push without the matching
path.pop()and the path never shrinks — you end up concatenating branches into one long garbage route. - Hardcoding the target. The target is
graph.length - 1, not a fixed number. Compute it from the input so the code works on graphs of any size. - Pushing the start node twice. The recursion begins with
dfs(0, [0])— node0is already in the path. Don't push it again inside the first frame.
Where this pattern shows up next
DFS on graphs branches into two families — mark-and-move traversal, and choose-explore-unchoose backtracking. These siblings cover both:
- Find if Path Exists in Graph — the yes/no version, where a visited set and a single traversal are enough.
- Clone Graph — DFS that builds a structure while walking, using a hash map to avoid re-cloning.
- Max Area of Island — grid DFS with visited marking, accumulating a value across the traversal.
- Redundant Connection — cycle detection via union-find, the tool you'd need if this graph weren't acyclic.
You can also step through All Paths From Source to Target interactively and watch the path array grow and rewind as each branch is explored.
FAQ
Why is there no visited set in the solution?
Because the input is a directed acyclic graph — there are no cycles, so a DFS can never loop forever. A visited set exists to stop traversal from revisiting nodes, but here a node legitimately belongs to many different paths. Marking it visited would block those alternate routes and drop valid answers. The DAG property is exactly what makes exhaustive enumeration safe without one.
Why must I copy the path before saving it?
The algorithm reuses one shared path array for efficiency, mutating it with push and pop as it explores. If you store a direct reference to that array, every entry in your results points at the same memory, which keeps changing during backtracking. When the search ends, all your "paths" show the final state. Writing allPaths.push([...path]) snapshots the current route so it stays frozen.
What is the time complexity, and can it be improved?
It is O(2ⁿ · n) in the worst case. A fully connected DAG where node i links to every later node produces up to 2ⁿ⁻² distinct paths, and each path takes up to O(n) to copy. This cannot be improved, because the output itself is exponential — you cannot enumerate 2ⁿ paths in fewer than 2ⁿ steps. The in-place backtracking does keep auxiliary space linear at O(n).
How is this different from Find if Path Exists in Graph?
That problem only needs a boolean: does any route connect source to destination? A single BFS or DFS with a visited set answers it in O(V + E). All Paths From Source to Target must produce every route explicitly, which is inherently exponential and requires backtracking rather than a one-shot traversal. Same DFS foundation, very different goal and cost.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.