Approach Summary
DFS from node 0. On reaching node n-1, record current path. Backtrack after exploring each neighbour. No revisit needed in a DAG.
How to Recognize This Pattern
- "All paths in a DAG from source to target"
- DFS + backtracking — no visited set needed in a DAG
Complexity Analysis
Time Complexity
O(2ⁿ × n)
Space Complexity
O(n)
Tags
Backtracking DFS BFS Graph