The problem
Given a DAG of n nodes labeled 0..n−1 as an adjacency list, return every possible path from node 0 to node n−1.
Stuck? Reveal hints one at a time
How to approach it
- 1Start DFS at node 0 with path = [0].
- 2At node u: if u is the target n−1, snapshot the current path into the results.
- 3Otherwise recurse into each neighbor, pushing it onto the path before and popping it after.
- 4Return all snapshots.
Key insight
The DAG guarantee removes the hardest part of path enumeration — cycle protection. Every DFS branch terminates on its own.
The solution
Watch out for
- Push a COPY of the path into results — pushing the live array gives you empty/shared paths after backtracking.
- Exponential output is inherent: a layered DAG can hold 2^(n/2) distinct paths.