All Paths From Source to Target

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 an adjacency list where graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to each node in graph[i]).

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: 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: There are five paths from node 0 to node 4.

Constraints

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i (no self-loops)
• All elements of graph[i] are unique.
• The input graph is a DAG.