Find All Routes From Start to End

Problem Statement

You are given a directed acyclic graph containing M nodes labeled from 0 to M-1. Your task is to find every possible route starting from node 0 and ending at node M-1 and return all these routes in any order.

The graph is represented as an array where the i-th element is a list of nodes that can be directly reached from node i.

Examples

Example 1:
Input: [[2,3], [4], [4], [4], []]
Output: [[0,2,4], [0,3,4], [0,2,4]]

Explanation:
The graph structure:
0 → 2 → 4
 \   \
  → 3 → 4
There are three routes from node 0 to node 4: 0→2→4, 0→3→4, and 0→2→4.
    

Example 2:
Input: [[1], [2], [3], []]
Output: [[0,1,2,3]]

Explanation:
The graph structure:
0 → 1 → 2 → 3
Only one route exists from node 0 to node 3.
    

Constraints

• The total number of nodes M is between 3 and 18 inclusive.
• The graph does not contain cycles (it's acyclic).
• Routes can be returned in any order, but the nodes in each route must be in traversal order.