DSA problem
All Paths From Source to Target
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order. The graph is given as graph, where graph[i] is a list of all nodes you can visit from node i (in other words, there is a directed edge from node i to each node graph[i][j]).
Because the graph is acyclic, there is no risk of infinite recursion and no need for a visited set — the only constraint is that we cannot revisit a node along the SAME path, which is automatically prevented in a DAG. The number of paths can be exponential in the worst case (a fully connected DAG produces up to 2^(n-2) paths), so any solution must in the worst case do exponential work just to write the answer; the algorithmic question is whether we waste time beyond that.
The optimal approach is straightforward DFS with path tracking. Maintain a mutable path array representing the current root-to-current sequence. At each call, append the current node. If it is the target (n - 1), append a snapshot of the path to the result. Otherwise recurse into every neighbor. After exploring all neighbors, pop the current node to restore the path for the caller (classic backtracking).
Total time is O(2^n * n) in the worst case — up to 2^(n-1) paths, each of length up to n. Space is O(n) for the recursion stack and the current path (excluding the size of the output itself).
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]]graph = [[1],[]][[0,1]]Constraints
- n == graph.length
- 2 <= n <= 15
- 0 <= graph[i][j] < n
- graph[i][j] != i (i.e., there are no self-loops).
- All the elements of graph[i] are unique.
- The input graph is guaranteed to be a DAG.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.