We’re preparing your current view and syncing the latest data.
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order. The graph is given as a list of lists, where graph[i] is a list of all nodes j for which the edge (i, j) exists.
An integer n representing the number of nodes, followed by a list of lists graph where graph[i] contains all nodes reachable from node i.
A list of lists, where each inner list represents a path from node 0 to node n - 1.
2 <= n <= 15; 0 <= graph[i][j] < n; graph[i][j] != i; The input graph is guaranteed to be a DAG.
Example 1
Input
[[1,2],[3],[3],[]]
Output
[[0,1,3],[0,2,3]]
Explanation
From node 0, you can go to node 1 or node 2. From both nodes 1 and 2, you can go to node 3 which is the target. Hence, paths are [0,1,3] and [0,2,3].
Example 2
Input
[[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
Multiple paths exist from node 0 to node 4 using various intermediate nodes.