All Paths From Source to Target
Last Updated: March 28, 2026
Understanding the Problem
We have a directed acyclic graph represented as an adjacency list, and we need to find every possible path from node 0 to node n - 1. The key word here is "all" paths, not the shortest or longest, but every single one.
Since the graph is a DAG, there are no cycles. This is important because it means we will never get stuck in an infinite loop during traversal. Every path we explore is guaranteed to terminate. Without cycles, we also do not need a "visited" set to prevent revisiting nodes. In fact, we must NOT use a global visited set, because the same node can appear in multiple valid paths.
The core observation is that this is a classic backtracking problem on a graph. We start at node 0, explore each neighbor, and when we reach node n - 1, we record the current path. Because the graph is acyclic, every recursive call eventually bottoms out.
Key Constraints:
2 <= n <= 15-> The graph is very small. With at most 15 nodes, even exponential algorithms are fine. In a DAG with n nodes, the maximum number of paths can be exponential (up to 2^(n-2) in a fully connected DAG), but with n = 15, that is at most 8192 paths.graph[i][j] != i-> No self-loops, confirming it is a proper DAG.The input graph is guaranteed to be a DAG-> No cycles, so DFS will always terminate without needing a visited set.
Approach 1: DFS with Backtracking
Intuition
The most natural way to find all paths in a graph is depth-first search. Start at node 0, pick a neighbor, go deeper, pick another neighbor, go deeper again, and so on. When you reach node n - 1, you have found a complete path. When you hit a dead end or finish exploring a branch, backtrack and try the next neighbor.
Because the graph is a DAG, we do not need a visited set. There are no cycles, so we will never loop back to a node we are currently visiting. This simplifies the code quite a bit. We just need to maintain a "current path" list, add nodes as we go deeper, and remove them when we backtrack.
Algorithm
- Create a result list to store all complete paths.
- Start a DFS from node
0with a current path containing just[0]. - At each node, check if it is the target node
n - 1. If yes, add a copy of the current path to the result. - Otherwise, iterate through all neighbors of the current node. For each neighbor, add it to the current path, recurse, then remove it (backtrack).
- Return the result list after DFS completes.
Example Walkthrough
Code
- Time Complexity: O(2^n * n). In the worst case, a DAG with n nodes can have up to 2^(n-2) paths from node 0 to node n-1. Each path can be up to length n, and copying a path takes O(n).
- Space Complexity: O(n). The recursion stack goes at most n levels deep. The current path list also holds at most n nodes. The output list is not counted as extra space.
This approach recomputes sub-paths from shared intermediate nodes. What if we explored paths layer by layer using BFS instead?
Approach 2: BFS with Path Tracking
Intuition
Instead of exploring depth-first, we can use breadth-first search. The twist is that a normal BFS only tracks which nodes to visit next. Here, we need to track the entire path leading to each node, because we need to output complete paths, not just reachability.
So each entry in the BFS queue is not just a node, but a full path from node 0 to that node. When we dequeue a path whose last node is the target, we add it to the result. Otherwise, we extend the path by appending each neighbor and enqueueing the extended paths.
Algorithm
- Initialize a queue with a single path
[0]. - Create a result list for complete paths.
- While the queue is not empty, dequeue a path.
- Check the last node in the path. If it is the target
n - 1, add the path to the result. - Otherwise, for each neighbor of the last node, create a new path by appending the neighbor, and enqueue it.
- Return the result list.
Example Walkthrough
Code
- Time Complexity: O(2^n * n). Same as DFS. We still visit every path, and each path has length up to n. The total number of paths is at most 2^(n-2), and copying/creating each path takes O(n).
- Space Complexity: O(2^n * n). The queue can hold up to 2^(n-2) partial paths simultaneously, each of length up to n. Much worse than the O(n) space of DFS backtracking.
BFS uses significantly more memory since it stores full path copies in the queue. What if we combined DFS with caching to avoid recomputing sub-paths from the same intermediate node?
Approach 3: DFS with Memoization
Intuition
Here is the key insight: in a DAG, the set of paths from any intermediate node X to the target is always the same, regardless of how we arrived at X. If nodes 1 and 2 both have edges to node 3, the paths from node 3 to the target are identical in both cases. The only difference is the prefix (how we got to node 3).
So instead of recomputing paths from node 3 to the target every time we visit it, we can cache them. The first time we visit node 3, we compute all paths from 3 to the target and store them. On subsequent visits, we just prepend the current prefix to each cached sub-path.
This is a top-down dynamic programming approach on the DAG. Since the graph is acyclic, there is a natural topological ordering, and memoization is guaranteed to work without circular dependencies.
In a DAG, the paths from any node X to the target form a fixed set that does not depend on how we reached X. This is the overlapping subproblems property that makes memoization effective. By caching allPaths(X) the first time we compute it, subsequent calls to allPaths(X) from other parent nodes return instantly.
The memoization does not change the worst-case time complexity, because we still have to construct and output every path. But in practice, it avoids redundant DFS traversals. If node X is reachable from k different parent nodes, plain DFS would traverse the entire subgraph rooted at X a total of k times. With memoization, we traverse it once and then reuse the cached sub-paths k-1 times.
Algorithm
- Create a memo dictionary that maps each node to a list of paths from that node to the target.
- Define a recursive function
allPaths(node)that returns all paths fromnodeto the target. - Base case: if
nodeis the target, return[[target]]. - If
nodeis already in the memo, return the cached result. - Otherwise, for each neighbor of
node, recursively get all paths fromneighborto the target. For each such path, prependnodeto it and add it to the result. - Cache the result in the memo and return it.
- Call
allPaths(0)to get the final answer.
Example Walkthrough
Code
- Time Complexity: O(2^n * n). The total number of paths is still up to 2^(n-2), and each path has length up to n. However, in practice, memoization avoids re-traversing subgraphs, making it faster than plain DFS on graphs with many converging paths.
- Space Complexity: O(2^n n). The memo stores all sub-paths from every reachable node. In the worst case, the total size of all cached paths is O(2^n n). This is more memory than the O(n) of DFS backtracking.