508. All Paths From Source to Target
You are given a directed acyclic graph (DAG) with n nodes numbered 0 through n − 1. It arrives as an adjacency list graph, where graph[i] holds every node reachable from node i along one directed edge.
Your function receives graph and must return every path that starts at node 0 and ends at node n − 1, each path given as the list of nodes it visits in order.
To keep the answer canonical, report the paths in depth-first discovery order: starting from node 0, always explore a node's neighbor list left to right, and emit a path the moment the walk reaches node n − 1.
Example 1:
Input: graph = [[1, 2], [3], [3], []]
Output: [[0, 1, 3], [0, 2, 3]]
Explanation: From node 0 you can step to 1 or 2, and both lead straight to node 3. DFS tries neighbor 1 first, so the path 0 → 1 → 3 is emitted before 0 → 2 → 3.
Example 2:
Input: graph = [[4, 3, 1], [3, 2, 4], [3], [4], []]
Output: [[0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4], [0, 1, 4]]
Explanation: Node 0's list is [4, 3, 1], so DFS first finds the direct edge 0 → 4, then the route through 3, then the three routes that begin 0 → 1.
Constraints:
- n == graph.length
- 2 ≤ n ≤ 15
- 0 ≤ graph[i][j] ≤ n - 1
- graph[i][j] ≠ i (no self-loops)
- All entries of graph[i] are distinct
- The graph is a DAG — it contains no directed cycles
Hints:
Because the graph is acyclic, a walk can never loop back onto its own path — you do not need a visited set, only systematic enumeration.
Run a DFS from node 0 carrying the current path in a list. On reaching node n − 1, record a **copy** of the path; otherwise recurse into each neighbor in list order and pop the node back off after the call returns.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: graph = [[1, 2], [3], [3], []]
Expected output: [[0, 1, 3], [0, 2, 3]]