All Paths From Source to Target
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, not one shortest path but the complete set.
Since the graph is a DAG, there are no cycles, so every traversal terminates. The absence of cycles also means a traversal cannot loop back to a node within a single path, so no "visited" set is needed to guarantee termination. A global visited set would be wrong here: the same node can appear in multiple valid paths, and marking it visited after the first path would suppress the others.
This is a backtracking problem on a graph. We start at node 0, explore each neighbor, and record the current path whenever we reach node n - 1. Because the graph is acyclic, every branch of the search bottoms out.
Key Constraints:
2 <= n <= 15-> The graph is small enough that exponential output is acceptable. A fully connected DAG has up to 2^(n-2) paths from node 0 to node n-1, which is 8192 for n = 15.graph[i][j] != i-> No self-loops.The input graph is guaranteed to be a DAG-> No cycles, so DFS terminates without a visited set.
Approach 1: DFS with Backtracking
Intuition
Depth-first search enumerates paths directly. Start at node 0, pick a neighbor, go deeper, pick another neighbor, go deeper again. Reaching node n - 1 completes a path. After finishing a branch, backtrack and try the next neighbor.
The only state we maintain is a single "current path" list: append a node when descending into it, remove it when backtracking. Since the DAG guarantee rules out cycles, the recursion cannot revisit a node within the current path and no visited set is needed.
Algorithm
- Create a result list to store all complete paths.
- Start a DFS from node
0with the current path initialized to[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.
The same enumeration can also run breadth-first, with the queue holding whole paths instead of single nodes.
Approach 2: BFS with Path Tracking
Intuition
A standard BFS queue holds single nodes, which is enough for reachability or shortest distance. To output complete paths, each queue entry must carry the entire path from node 0 to its last node.
So each entry in the queue is a full path. 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 of the last node and enqueue the extended copies. No visited set appears here either, for the same reason as in DFS: a node can belong to many paths. Replacing the queue with a stack gives an iterative depth-first version of the same idea; the paths come out in a different order.
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 stores full path copies in the queue, which costs far more memory than the DFS recursion stack. Both approaches also re-traverse the subgraph below a node once for every way of reaching that node. Caching sub-paths removes that repeated traversal.
Approach 3: DFS with Memoization
Intuition
In a DAG, the set of paths from any intermediate node X to the target is 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; only the prefix differs.
So instead of recomputing paths from node 3 to the target on every visit, cache them. The first call to allPaths(3) computes and stores every path from 3 to the target. Later calls return the cached list, and each caller prepends its own node to every cached sub-path.
This is top-down dynamic programming on the DAG. Acyclicity guarantees the recursion has no circular dependencies. The same computation can run bottom-up by processing nodes in reverse topological order and filling the table from the target backwards; the cached contents come out identical.
Memoization removes repeated traversal, not output work. If node X is reachable from k different parent nodes, plain DFS traverses the entire subgraph below X a total of k times; with the cache, that subgraph is traversed once and the stored sub-paths are reused k - 1 times.
The worst-case time complexity does not improve, because the answer itself can contain up to 2^(n-2) paths of length up to n, and every output path still has to be constructed and copied.
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. - If
nodeis already in the memo, return the cached result. - Base case: if
nodeis the target, cache and return[[target]]. - 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 output can contain up to 2^(n-2) paths of length up to n, and each output path still takes O(n) to build, so memoization does not improve the worst-case bound. What it eliminates is the repeated traversal of shared subgraphs, which is pure traversal work, not output work.
- Space Complexity: O(2^n n). The memo stores all sub-paths from every reachable node, so the total cached size is O(2^n n) in the worst case, far more than the O(n) recursion stack of plain DFS backtracking.