Enumerate every directed path from node 0 to the last node in a directed acyclic graph.
Problem
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.
Goal
Find every complete source-to-target route by exploring the graph and collecting each path when the target is reached.
Input Format
graph: an adjacency list wheregraph[i]contains all nodes directly reachable from nodei.- Node
0is the start node. - Node
n - 1is the destination node.
Output Format
Return a list of paths, where each path is a list of integers from 0 to n - 1.
Constraints
2 <= n- The graph is directed and acyclic.
- Each node label is in
[0, n - 1]. - The number of valid paths can be large, so the output may grow exponentially in the worst case.
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
Unlock deeper context for this problem
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.