177. All Paths From Source to Target

Medium · Graph

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`. The graph is given as an adjacency list where `graph[i]` is a list of all nodes you can visit from node `i`.

Return all paths from source node `0` to target node `n-1`. Each path should be represented as a list of node labels. The answer may be returned in any order, but for this platform paths are sorted: each path is listed in traversal order, and the list of paths is sorted lexicographically.

Note: The graph is guaranteed to be a DAG (no cycles), so you do not need to worry about infinite loops.

Examples

Example 1
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths from node 0 to node 3 (n-1=3): 0→1→3 and 0→2→3.
Example 2
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,1,2,3,4],[0,1,3,4],[0,1,4],[0,3,4],[0,4]]
Explanation: There are five paths from node 0 to node 4. All are listed in lexicographic order.

Constraints