All Paths From Source to Target
You are given a directed acyclic graph (DAG) represented as an adjacency list. graph[i] is a list of all nodes you can visit from node i. Find all possible paths from node 0 to node n-1, where n is the number of nodes.
This is LeetCode 797: All Paths From Source to Target, and it is one of the cleanest problems for learning DFS with backtracking on graphs. The DAG constraint removes the need for a visited set, letting you focus purely on the recursive exploration logic.
Why this problem matters
DAG traversal and backtracking are two patterns that show up constantly in graph problems. This problem combines them in the most direct way possible: enumerate every path from a source to a target in a directed graph with no cycles.
Unlike problems where you need to find the shortest path or detect cycles, here you need to find all paths. That means you cannot stop at the first answer. You have to explore every branch of the search tree, collecting valid paths as you go. This is exactly what backtracking is designed for.
The DAG guarantee is what makes this problem clean. In a graph with cycles, you would need a visited set to avoid infinite loops. Since a DAG has no cycles by definition, you never revisit a node within the same path. That means the DFS can freely recurse into any neighbor without checking if it has been seen before.
Understanding this problem gives you a template you can adapt for harder problems: finding all combinations, generating permutations, solving constraint satisfaction problems. The backtracking skeleton is always the same.
The approach: DFS with backtracking
The idea is simple. Start at node 0 with a path containing just [0]. At each node, try every neighbor. Append the neighbor to the path, recurse, then pop it off (backtrack). If you ever reach node n-1, copy the current path into the result list.
Why does this work? Because the graph is a DAG:
- No cycles means the recursion always terminates. Every step moves along a directed edge, and since there are no cycles, you cannot loop back.
- No visited set needed. A node can appear in multiple paths (node 2 appears in both
[0, 1, 2, 3]and[0, 2, 3]), and that is fine. We just cannot visit the same node twice within a single path, which the DAG structure prevents automatically. - Backtracking ensures we explore every possible branch. After recording one path, we undo the last choice (pop the node) and try the next neighbor.
The key difference from cycle-containing graphs: you do not need a visited set. The DAG structure guarantees you will never loop, so every recursive call eventually hits the target or a dead end.
The solution
def all_paths_source_target(graph):
target = len(graph) - 1
result = []
def dfs(node, path):
if node == target:
result.append(path[:])
return
for neighbor in graph[node]:
path.append(neighbor)
dfs(neighbor, path)
path.pop()
dfs(0, [0])
return result
Let's walk through the key details.
The target is always len(graph) - 1 because the nodes are numbered 0 to n-1. The result list collects all valid paths.
The dfs function takes the current node and the path built so far. When node == target, we have found a complete path. We append a copy of the path (path[:]) to the result. Why a copy? Because the same path list gets mutated as we backtrack. If we stored a reference instead of a copy, every entry in result would point to the same list, and they would all end up containing whatever the path looked like at the end of the algorithm.
For each neighbor of the current node, we append it to the path, recurse, then pop it off. That pop is the backtracking step. It restores the path to its state before we explored that neighbor, so the next iteration of the loop can try a different neighbor cleanly.
The initial call dfs(0, [0]) starts at node 0 with the path already containing the source.
Visual walkthrough
Let's trace the DFS through the graph [[1, 2], [3, 2], [3], []]. Node 0 connects to 1 and 2. Node 1 connects to 3 and 2. Node 2 connects to 3. Node 3 is the target with no outgoing edges.
Step 1: Start DFS at node 0. path = [0].
Node 0 is the source. We begin DFS and add 0 to the current path.
Step 2: Explore neighbor 1. path = [0, 1].
Node 0's first neighbor is 1. Append 1 to the path and recurse.
Step 3: From 1, explore neighbor 3. Target reached! Record [0, 1, 3].
Node 3 is the target. Copy the current path into result. Then backtrack (pop 3).
Step 4: Backtrack to 1. Explore neighbor 2, then 2's neighbor 3. Record [0, 1, 2, 3].
From node 1's second neighbor (2), we continue to 3. Another path found. Backtrack all the way to node 0.
Step 5: Back at 0. Explore neighbor 2, then 3. Record [0, 2, 3]. Done!
Node 0's second neighbor is 2. From 2 we reach 3 again. All neighbors explored. DFS complete with 3 paths.
Notice how backtracking works in practice. After recording [0, 1, 3] in step 3, the algorithm pops 3 off the path, returning to [0, 1]. From node 1 it then explores the next neighbor (2), which leads to 3 again, recording [0, 1, 2, 3]. Then it backtracks all the way to node 0 and explores its second neighbor (2), finding the final path [0, 2, 3].
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(2^n * n) |
| Space | O(n) |
Time: In the worst case, a DAG can have an exponential number of paths from source to target. Consider a graph where every node connects to every node with a higher number. The number of paths can be 2^(n-2), and each path can be up to length n. So the total work is O(2^n * n). For the typical LeetCode constraints (n up to 15), this is perfectly fine.
Space: The recursion depth is at most n (the longest path from source to target). The path list also holds at most n nodes at any time. The result list itself can hold O(2^n) paths, but that is output space, not auxiliary space. The auxiliary space for the DFS is O(n).
The building blocks
This problem is built on two reusable pieces that come up across many backtracking and graph problems.
1. DFS path enumeration
The pattern of recursively exploring all branches and collecting valid results:
def dfs(node, path):
if is_goal(node):
result.append(path[:])
return
for next_node in neighbors(node):
path.append(next_node)
dfs(next_node, path)
path.pop()
This is the same skeleton used in Combination Sum, Subsets, Permutations, and dozens of other backtracking problems. The only things that change are the goal condition and how you generate the next choices.
2. DAG traversal without a visited set
In a DAG, you can freely recurse without worrying about cycles. This pattern shows up in Course Schedule (topological sort) and any problem involving dependency graphs. The absence of cycles simplifies the code because you skip the visited-set bookkeeping entirely.
If the graph could contain cycles, you would need to add a visited set or track the current path to prevent infinite recursion. The DAG constraint is what lets this solution be so concise.
Edge cases
- Single node:
graph = [[]]. Node 0 is both the source and the target. The DFS immediately hits the base case and returns[[0]]. - Linear graph:
graph = [[1], [2], [3], []]. Only one path exists:[0, 1, 2, 3]. The DFS goes straight through with no branching. - Fully connected DAG: every node connects to all higher-numbered nodes. This produces the maximum number of paths (exponential). The algorithm handles it correctly but takes longer.
- No path to target: this cannot happen in the problem's constraints (the graph is guaranteed to have paths from 0 to n-1), but if it did, the result would simply be an empty list because no DFS branch would reach the target.
From understanding to recall
You have seen how DFS with backtracking explores every path in a DAG. The code is short: a base case, a loop over neighbors, append, recurse, pop. It all makes sense on paper.
But writing it from scratch under time pressure is different. Will you remember to copy the path with path[:] instead of appending a reference? Will the backtracking pop() be in the right place? Will you set up the initial call with dfs(0, [0]) correctly?
These details become automatic with spaced repetition. You write the DFS backtracking skeleton from memory at increasing intervals until it flows out naturally. When a graph path enumeration problem appears in your interview, you do not need to re-derive the pattern. You just write it.
Related posts
- Number of Islands - Grid DFS traversal, the foundational graph search pattern
- Course Schedule - DAG cycle detection and topological sort, another core DAG pattern
- Clone Graph - Graph DFS with a hash map, showing how traversal patterns adapt to different goals
CodeBricks breaks All Paths From Source to Target into its DFS-backtracking and DAG-traversal building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a backtracking graph problem appears in your interview, you do not hesitate. You just write it.