Enumerate every directed path from node 0 to the last node in a directed acyclic graph.
You are given a directed graph with n nodes labeled from 0 to n - 1, represented as an adjacency list. Node 0 is the source and node n - 1 is the target.
Return all possible paths from node 0 to node n - 1.
A path should be represented as a list of node labels in the order they are visited.
Because the graph is directed and acyclic, every valid route is finite. The answer may be returned in any order.
Find every complete source-to-target route by exploring the graph and collecting each path when the target is reached.
graph: an adjacency list where graph[i] contains all nodes directly reachable from node i.0 is the start node.n - 1 is the destination node.Return a list of paths, where each path is a list of integers from 0 to n - 1.
2 <= n[0, n - 1].Example 1
Input
graph = [[1,2],[3],[3],[]]
Output
[[0,1,3],[0,2,3]]
Explanation
There are two paths from 0 to 3: 0 → 1 → 3 and 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
Each complete route from node 0 to node 4 is included once.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.