All Paths From Source to Target (LeetCode 797)
A directed graph has n nodes, numbered 0 to n - 1, and it has no cycle. A directed graph with no cycle is called a DAG. An edge goes from one node to another and can be followed in that direction only.
The graph is given as graph, an adjacency list: graph[i] lists every node that node i has an edge to. A path is a list of nodes in which each node has an edge to the next one.
Find every path that starts at node 0 and ends at node n - 1. Return all of them, in any order.
Worked Examples
graph = [[1,2],[3],[3],[]][[0,1,3],[0,2,3]]graph = [[4,3,1],[3,2,4],[3],[4],[]][[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]⚖️Formal Constraints & Bounds
n == graph.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i(there are no self-loops)All the elements of
graph[i]are unique.The input graph is guaranteed to be a DAG.
Core Insight
A path is a list that grows when the walk goes down an edge and shrinks when it comes back. Append a node before the call, pop it after the call, and save a copy at the target. A node can lie on several paths, and every path is a separate answer, so the walk keeps no visited set.
Real-World Scenario & Production Applications
A build tool has tasks that depend on each other, and a report must list every chain of tasks from the first task to the last one. Each chain follows the arrows of the dependency graph, and a chain never repeats a task, because the graph has no cycle.
Step-by-Step Execution Trace Table
Example 1, graph = [[1,2],[3],[3],[]], so target = 3. The columns show the state after each row:
| Step | What runs | path | paths | What it means |
|---|---|---|---|---|
| 1 | path = [0], dfs(0) | [0] | [] | The walk starts at the source |
| 2 | path.append(1), dfs(1) | [0, 1] | [] | The first neighbour of node 0 |
| 3 | path.append(3), dfs(3) | [0, 1, 3] | [] | Node 3 is the target |
| 4 | paths.append(path[:]) | [0, 1, 3] | [[0, 1, 3]] | A copy is saved, and the call returns |
| 5 | path.pop() twice | [0] | [[0, 1, 3]] | Node 3 and then node 1 leave the path |
| 6 | path.append(2), dfs(2) | [0, 2] | [[0, 1, 3]] | The second neighbour of node 0 |
| 7 | path.append(3), dfs(3) | [0, 2, 3] | [[0, 1, 3]] | Node 3 is reached a second time, by a different path |
| 8 | paths.append(path[:]) | [0, 2, 3] | [[0, 1, 3], [0, 2, 3]] | A second copy is saved |
| 9 | path.pop() twice | [0] | [[0, 1, 3], [0, 2, 3]] | The loop over node 0 is finished |
With a seen set, step 7 would skip node 3 and the answer would be [[0, 1, 3]]. Saving path without the copy [:] would return [[0], [0]].
graph = [[1,2],[3],[3],[]][[0,1,3],[0,2,3]]Example 1, graph = [[1,2],[3],[3],[]], so target = 3. The columns show the state after each row:
| Step | What runs | path | paths | What it means |
|---|---|---|---|---|
| 1 | path = [0], dfs(0) | [0] | [] | The walk starts at the source |
| 2 | path.append(1), dfs(1) | [0, 1] | [] | The first neighbour of node 0 |
| 3 | path.append(3), dfs(3) | [0, 1, 3] | [] | Node 3 is the target |
| 4 | paths.append(path[:]) | [0, 1, 3] | [[0, 1, 3]] | A copy is saved, and the call returns |
| 5 | path.pop() twice | [0] | [[0, 1, 3]] | Node 3 and then node 1 leave the path |
| 6 | path.append(2), dfs(2) | [0, 2] | [[0, 1, 3]] | The second neighbour of node 0 |
| 7 | path.append(3), dfs(3) | [0, 2, 3] | [[0, 1, 3]] | Node 3 is reached a second time, by a different path |
| 8 | paths.append(path[:]) | [0, 2, 3] | [[0, 1, 3], [0, 2, 3]] | A second copy is saved |
| 9 | path.pop() twice | [0] | [[0, 1, 3], [0, 2, 3]] | The loop over node 0 is finished |
With a seen set, step 7 would skip node 3 and the answer would be [[0, 1, 3]]. Saving path without the copy [:] would return [[0], [0]].
| 1 | target = len(graph) - 1 |
| 2 | paths = [] |
| 3 | path = [0] |
| 4 | dfs(node): |
| 5 | if node == target: paths.append(path[:]) and return |
| 6 | for nxt in graph[node]: |
| 7 | path.append(nxt) |
| 8 | dfs(nxt) |
| 9 | path.pop() |
| 10 | dfs(0) |
| 11 | return paths |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A directed graph is stored as an adjacency list: graph[i] lists every node that node i has an edge to. In All Paths From Source to Target, the graph has no cycle, and the answer lists every path from node 0 to node n - 1.
The code walks the graph with a depth-first search, and it keeps one shared list, path. The list always holds the nodes from node 0 to the node being visited. This list is the result that the walk carries along.
📓 The Analogy: A Route Written In A Notebook
You walk through rooms, and a notebook holds the rooms of your route in order. When you enter a room, you write its number at the end of the list. When you walk back, you cross out the last number. When you reach the exit room, you copy the whole list onto a new page. The copy matters, because the notebook keeps changing as you walk on. A room that you reach by two different routes is written down twice, once for each route.
🔑 The Key Idea in the Code
Three lines carry the idea. paths.append(path[:]) saves a copy at the target. path.append(nxt) before dfs(nxt) and path.pop() after it keep path correct for every neighbour. There is no seen set: Number of Islands marks a cell once because it needs each cell once, but this problem needs each path once, and one node can lie on many paths.
Adding the times of the branches instead of taking the longest: employees at the same level hear the news at the same moment, so the answer is the largest carried value, not a sum. For
manager = [-1,0,0,1,2]andinformTime = [2,5,3,0,0]the sum is 10 and the answer is 7.Adding
informTime[report]instead ofinformTime[employee]: a subordinate hears the news after the manager's time, not after their own. With the wrong index, the head's own time is never counted.Searching with recursion: a chain of 100000 employees needs 100000 nested calls. Python's default recursion limit is 1000, so a recursive
dfsraises a RecursionError. The explicitstackhas no such limit.Keeping a visited set: the manager list is a tree, so each employee is reached exactly once. A set adds memory and removes nothing.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Find all possible paths" from one node to another asks for a list of answers, not a count and not a yes or no. "Directed acyclic graph" means no walk can go around a cycle, so the walk always ends. With n <= 15, the largest answer has 2^13 paths, so listing them all is affordable. This is Graph Paths: one shared path, a copy at the target.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
When dfs(node) is called, path holds the nodes from node 0 to node. When dfs(node) returns, path is the same as before the call. At target, path[:] is one complete answer. Each edge of graph[node] is tried once, so each path is found once.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
paths.append(path[:]), neverpaths.append(path): by the end everypath.pop()has run, so every saved answer is the same list.[[1,2],[3],[3],[]]returns[[0], [0]].path.pop()afterdfs(nxt): without it, the nodes of the first path stay inpath, and[[1,2],[3],[3],[]]returns[[0, 1, 3], [0, 1, 3, 2, 3]].No
seenset: a node on two paths must be walked twice. Withif nxt in seen: continue,[[1,2],[3],[3],[]]returns[[0, 1, 3]]and loses[0, 2, 3].The graph has no cycle, which LeetCode promises. On
[[1],[0,2],[]]the same walk never ends and Python raises a RecursionError, because node 1 leads back to node 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with a depth-first search that carries one shared path. The graph is an adjacency list, and it has no cycle. I keep a list called path that starts with node 0. For each neighbour, I append it to path, call dfs on it, and pop it when the call returns, so path always holds the nodes from node 0 to the node I am visiting. When the node is the last one, I save a copy of path, because path keeps changing. I keep no visited set. A node can lie on many paths, and each path is a separate answer, so a visited set would drop real answers. Because the graph has no cycle, every walk ends. In the worst case every node points to every later node, so there are 2 to the power of n minus 2 paths, each up to n long. The time is order 2 to the n times n. The extra space is order n for path and the recursion, not counting the answer itself.
Complexity & Mathematical Proof
O(2^V * V)
Look at the code: every call of dfs is made for a node at the end of a path that starts at node 0, and the graph has no cycle, so a path never repeats a node. In the worst case every node has an edge to every later node. Then each subset of the middle nodes is a path, so there are 2^(V - 2) paths from node 0 to node n - 1. Each call does constant work, plus one copy of path when the call is at the target, and a copy costs up to V. The calls that do not reach the target are prefixes of paths, so there are at most 2^(V - 1) of them. Total: O(2^V * V).
O(V)
path holds at most V nodes, because a path never repeats a node. The recursion is at most V calls deep for the same reason. paths holds the answer, which is the output and is not counted. Auxiliary space: O(V).
Derivation Progression
2^{V-2} paths in the worst case
When every node has an edge to every later node, each subset of the V - 2 middle nodes gives one path from node 0 to node n - 1.
paths.append(path[:]) copies at most V nodes each time a path is saved.
at most 2^{V-1} calls of O(1) work
Every call of dfs is a path that starts at node 0, so a call never repeats, and the work outside the copies is constant per call.
Variable Definitions
Number of nodes, n = len(graph)
Memory Architecture & Bounds
O(V): at most V nested calls, because a path never repeats a node
O(V): path holds at most V nodes
O(2^V * V): the list of all paths, which is the answer
Boundary Best / Worst Cases
when the graph is one chain: a single path exists and each node is visited once.
, where is the number of paths in the answer.
when every node has an edge to every later node.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "find all possible paths", "directed acyclic graph". The answer is a list of paths, so the output sets the cost. One shared path with an append before the call and a pop after it builds each path without rebuilding it from node 0.
, so the largest answer, a DAG where every node has an edge to every later node, has paths of up to 15 nodes. The cost is , set by the output. The recursion is at most 15 calls deep, so Python's recursion limit does not matter here.
Save path[:], never path: [[1,2],[3],[3],[]] returns [[0], [0]]. Keep no visited set, or [0, 2, 3] is lost. On a graph with a cycle the walk never ends, so a caller that cannot promise a DAG needs a check if nxt in path: continue, or the three colors of Cycle Detection. All paths are stored in memory, so a larger graph needs a generator that yields each path.
Core Algorithmic State Invariants
- Example 1, Two Paths Through Node 3
In graph = [[1,2],[3],[3],[]], the walk reaches node 3 through node 1 and saves [0, 1, 3]. After two pops, it goes to node 2, reaches node 3 a second time and saves [0, 2, 3]. Both paths are found because no visited set blocks the second visit.
- path Is Restored After Every Call
dfs(nxt) returns with path exactly as it was before path.append(nxt), because path.pop() runs right after the call. So the next neighbour of the same node extends the same path, not the path of the previous neighbour.
- The Copy Is What Survives
paths.append(path[:]) stores the values that path holds at that moment. The list path keeps changing, and when the walk ends it is [0] again. Storing path without the copy returns [[0], [0]] for Example 1.
All Paths From Source to Target (LeetCode 797)
A directed graph has n nodes, numbered 0 to n - 1, and it has no cycle. A directed graph with no cycle is called a DAG. An edge goes from one node to another and can be followed in that direction only.
The graph is given as graph, an adjacency list: graph[i] lists every node that node i has an edge to. A path is a list of nodes in which each node has an edge to the next one.
Find every path that starts at node 0 and ends at node n - 1. Return all of them, in any order.
Worked Examples
graph = [[1,2],[3],[3],[]][[0,1,3],[0,2,3]]graph = [[4,3,1],[3,2,4],[3],[4],[]][[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]⚖️Formal Constraints & Bounds
n == graph.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i(there are no self-loops)All the elements of
graph[i]are unique.The input graph is guaranteed to be a DAG.
Core Insight
A path is a list that grows when the walk goes down an edge and shrinks when it comes back. Append a node before the call, pop it after the call, and save a copy at the target. A node can lie on several paths, and every path is a separate answer, so the walk keeps no visited set.
Real-World Scenario & Production Applications
A build tool has tasks that depend on each other, and a report must list every chain of tasks from the first task to the last one. Each chain follows the arrows of the dependency graph, and a chain never repeats a task, because the graph has no cycle.
Step-by-Step Execution Trace Table
Example 1, graph = [[1,2],[3],[3],[]], so target = 3. The columns show the state after each row:
| Step | What runs | path | paths | What it means |
|---|---|---|---|---|
| 1 | path = [0], dfs(0) | [0] | [] | The walk starts at the source |
| 2 | path.append(1), dfs(1) | [0, 1] | [] | The first neighbour of node 0 |
| 3 | path.append(3), dfs(3) | [0, 1, 3] | [] | Node 3 is the target |
| 4 | paths.append(path[:]) | [0, 1, 3] | [[0, 1, 3]] | A copy is saved, and the call returns |
| 5 | path.pop() twice | [0] | [[0, 1, 3]] | Node 3 and then node 1 leave the path |
| 6 | path.append(2), dfs(2) | [0, 2] | [[0, 1, 3]] | The second neighbour of node 0 |
| 7 | path.append(3), dfs(3) | [0, 2, 3] | [[0, 1, 3]] | Node 3 is reached a second time, by a different path |
| 8 | paths.append(path[:]) | [0, 2, 3] | [[0, 1, 3], [0, 2, 3]] | A second copy is saved |
| 9 | path.pop() twice | [0] | [[0, 1, 3], [0, 2, 3]] | The loop over node 0 is finished |
With a seen set, step 7 would skip node 3 and the answer would be [[0, 1, 3]]. Saving path without the copy [:] would return [[0], [0]].
graph = [[1,2],[3],[3],[]][[0,1,3],[0,2,3]]Example 1, graph = [[1,2],[3],[3],[]], so target = 3. The columns show the state after each row:
| Step | What runs | path | paths | What it means |
|---|---|---|---|---|
| 1 | path = [0], dfs(0) | [0] | [] | The walk starts at the source |
| 2 | path.append(1), dfs(1) | [0, 1] | [] | The first neighbour of node 0 |
| 3 | path.append(3), dfs(3) | [0, 1, 3] | [] | Node 3 is the target |
| 4 | paths.append(path[:]) | [0, 1, 3] | [[0, 1, 3]] | A copy is saved, and the call returns |
| 5 | path.pop() twice | [0] | [[0, 1, 3]] | Node 3 and then node 1 leave the path |
| 6 | path.append(2), dfs(2) | [0, 2] | [[0, 1, 3]] | The second neighbour of node 0 |
| 7 | path.append(3), dfs(3) | [0, 2, 3] | [[0, 1, 3]] | Node 3 is reached a second time, by a different path |
| 8 | paths.append(path[:]) | [0, 2, 3] | [[0, 1, 3], [0, 2, 3]] | A second copy is saved |
| 9 | path.pop() twice | [0] | [[0, 1, 3], [0, 2, 3]] | The loop over node 0 is finished |
With a seen set, step 7 would skip node 3 and the answer would be [[0, 1, 3]]. Saving path without the copy [:] would return [[0], [0]].
| 1 | target = len(graph) - 1 |
| 2 | paths = [] |
| 3 | path = [0] |
| 4 | dfs(node): |
| 5 | if node == target: paths.append(path[:]) and return |
| 6 | for nxt in graph[node]: |
| 7 | path.append(nxt) |
| 8 | dfs(nxt) |
| 9 | path.pop() |
| 10 | dfs(0) |
| 11 | return paths |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A directed graph is stored as an adjacency list: graph[i] lists every node that node i has an edge to. In All Paths From Source to Target, the graph has no cycle, and the answer lists every path from node 0 to node n - 1.
The code walks the graph with a depth-first search, and it keeps one shared list, path. The list always holds the nodes from node 0 to the node being visited. This list is the result that the walk carries along.
📓 The Analogy: A Route Written In A Notebook
You walk through rooms, and a notebook holds the rooms of your route in order. When you enter a room, you write its number at the end of the list. When you walk back, you cross out the last number. When you reach the exit room, you copy the whole list onto a new page. The copy matters, because the notebook keeps changing as you walk on. A room that you reach by two different routes is written down twice, once for each route.
🔑 The Key Idea in the Code
Three lines carry the idea. paths.append(path[:]) saves a copy at the target. path.append(nxt) before dfs(nxt) and path.pop() after it keep path correct for every neighbour. There is no seen set: Number of Islands marks a cell once because it needs each cell once, but this problem needs each path once, and one node can lie on many paths.
Adding the times of the branches instead of taking the longest: employees at the same level hear the news at the same moment, so the answer is the largest carried value, not a sum. For
manager = [-1,0,0,1,2]andinformTime = [2,5,3,0,0]the sum is 10 and the answer is 7.Adding
informTime[report]instead ofinformTime[employee]: a subordinate hears the news after the manager's time, not after their own. With the wrong index, the head's own time is never counted.Searching with recursion: a chain of 100000 employees needs 100000 nested calls. Python's default recursion limit is 1000, so a recursive
dfsraises a RecursionError. The explicitstackhas no such limit.Keeping a visited set: the manager list is a tree, so each employee is reached exactly once. A set adds memory and removes nothing.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Find all possible paths" from one node to another asks for a list of answers, not a count and not a yes or no. "Directed acyclic graph" means no walk can go around a cycle, so the walk always ends. With n <= 15, the largest answer has 2^13 paths, so listing them all is affordable. This is Graph Paths: one shared path, a copy at the target.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
When dfs(node) is called, path holds the nodes from node 0 to node. When dfs(node) returns, path is the same as before the call. At target, path[:] is one complete answer. Each edge of graph[node] is tried once, so each path is found once.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
paths.append(path[:]), neverpaths.append(path): by the end everypath.pop()has run, so every saved answer is the same list.[[1,2],[3],[3],[]]returns[[0], [0]].path.pop()afterdfs(nxt): without it, the nodes of the first path stay inpath, and[[1,2],[3],[3],[]]returns[[0, 1, 3], [0, 1, 3, 2, 3]].No
seenset: a node on two paths must be walked twice. Withif nxt in seen: continue,[[1,2],[3],[3],[]]returns[[0, 1, 3]]and loses[0, 2, 3].The graph has no cycle, which LeetCode promises. On
[[1],[0,2],[]]the same walk never ends and Python raises a RecursionError, because node 1 leads back to node 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with a depth-first search that carries one shared path. The graph is an adjacency list, and it has no cycle. I keep a list called path that starts with node 0. For each neighbour, I append it to path, call dfs on it, and pop it when the call returns, so path always holds the nodes from node 0 to the node I am visiting. When the node is the last one, I save a copy of path, because path keeps changing. I keep no visited set. A node can lie on many paths, and each path is a separate answer, so a visited set would drop real answers. Because the graph has no cycle, every walk ends. In the worst case every node points to every later node, so there are 2 to the power of n minus 2 paths, each up to n long. The time is order 2 to the n times n. The extra space is order n for path and the recursion, not counting the answer itself.
Complexity & Mathematical Proof
O(2^V * V)
Look at the code: every call of dfs is made for a node at the end of a path that starts at node 0, and the graph has no cycle, so a path never repeats a node. In the worst case every node has an edge to every later node. Then each subset of the middle nodes is a path, so there are 2^(V - 2) paths from node 0 to node n - 1. Each call does constant work, plus one copy of path when the call is at the target, and a copy costs up to V. The calls that do not reach the target are prefixes of paths, so there are at most 2^(V - 1) of them. Total: O(2^V * V).
O(V)
path holds at most V nodes, because a path never repeats a node. The recursion is at most V calls deep for the same reason. paths holds the answer, which is the output and is not counted. Auxiliary space: O(V).
Derivation Progression
2^{V-2} paths in the worst case
When every node has an edge to every later node, each subset of the V - 2 middle nodes gives one path from node 0 to node n - 1.
paths.append(path[:]) copies at most V nodes each time a path is saved.
at most 2^{V-1} calls of O(1) work
Every call of dfs is a path that starts at node 0, so a call never repeats, and the work outside the copies is constant per call.
Variable Definitions
Number of nodes, n = len(graph)
Memory Architecture & Bounds
O(V): at most V nested calls, because a path never repeats a node
O(V): path holds at most V nodes
O(2^V * V): the list of all paths, which is the answer
Boundary Best / Worst Cases
when the graph is one chain: a single path exists and each node is visited once.
, where is the number of paths in the answer.
when every node has an edge to every later node.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "find all possible paths", "directed acyclic graph". The answer is a list of paths, so the output sets the cost. One shared path with an append before the call and a pop after it builds each path without rebuilding it from node 0.
, so the largest answer, a DAG where every node has an edge to every later node, has paths of up to 15 nodes. The cost is , set by the output. The recursion is at most 15 calls deep, so Python's recursion limit does not matter here.
Save path[:], never path: [[1,2],[3],[3],[]] returns [[0], [0]]. Keep no visited set, or [0, 2, 3] is lost. On a graph with a cycle the walk never ends, so a caller that cannot promise a DAG needs a check if nxt in path: continue, or the three colors of Cycle Detection. All paths are stored in memory, so a larger graph needs a generator that yields each path.
Core Algorithmic State Invariants
- Example 1, Two Paths Through Node 3
In graph = [[1,2],[3],[3],[]], the walk reaches node 3 through node 1 and saves [0, 1, 3]. After two pops, it goes to node 2, reaches node 3 a second time and saves [0, 2, 3]. Both paths are found because no visited set blocks the second visit.
- path Is Restored After Every Call
dfs(nxt) returns with path exactly as it was before path.append(nxt), because path.pop() runs right after the call. So the next neighbour of the same node extends the same path, not the path of the previous neighbour.
- The Copy Is What Survives
paths.append(path[:]) stores the values that path holds at that moment. The list path keeps changing, and when the walk ends it is [0] again. Storing path without the copy returns [[0], [0]] for Example 1.