A directed acyclic graph with n nodes 0 .. n-1 is given as a list of lists: graph[i] holds the
nodes that node i has an edge to. Return every path from node 0 to node n-1, each path as a list of
node labels. The paths may be returned in any order.
Examples
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
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]]
Constraints
1 <= n <= 18; the graph has no cycles.- Target
O(paths * n)time; each path is reported once.
Goals
- Enumerate paths with a DFS that carries the current path
- Recognise that a DAG needs no visited set for path enumeration