Description
Given a directed acyclic graph of n nodes, find all possible paths from node 0 to node n-1 and return them in any order.
Examples
Input:
graph = [[1,2],[3],[3],[]]Output:
[[0,1,3],[0,2,3]]Explanation:
Two paths to end.
Input:
graph = [[1],[2],[]]Output:
[[0,1,2]]Explanation:
Simple linear path case. Starting from node 0, it is possible to only go to node 1, then from node 1 it is possible to only go to node 2 (the target). There is exactly one path from source to target.
Input:
graph = [[1,2,3],[4],[4],[4],[]]Output:
[[0,1,4],[0,2,4],[0,3,4]]Explanation:
Multiple direct paths to target. From node 0, there are three choices (nodes 1, 2, or 3), but all of them lead directly to node 4 (the target). This creates three distinct paths, each with exactly 3 nodes.
Constraints
- •
2 ≤ n ≤ 15