All Paths From Source to Target

Statement

You are given a directed acyclic graph (DAG) with $n$ nodes, labeled from $0$ to $n - 1$. The graph is represented as an adjacency list, where graph[i] is a list of all nodes to which node i has a directed edge to.

Your task is to find all possible paths from node $0$ (the source) to node $n - 1$ (the target) and return them as a list of paths. Each path should be represented as a list of node indexes.

Note: You may return the answer in any order.

Constraints:

• $2 \leq$ $n$ $\leq 15$

• $0 \leq$ graph[i][j] $<$ $n$

• All nodes in graph[i] are unique.

• The graph is guaranteed to be a DAG (no cycles).

• There are no self-loops (i.e., graph[i] does not contain i).

Examples