640. Every Route Out
A one-way road network has n junctions numbered 0 to n - 1. The array graph describes it: graph[i] lists every junction that can be reached by a road directly from junction i. The roads contain no cycles.
Return all routes that lead from junction 0 to the last junction n - 1. Each route is the list of junctions in the order they are visited, starting with 0 and ending with n - 1. The routes may be returned in any order. If n = 1 the only route is [0].
Example 1
- Input:
- graph = [[1,2],[3],[3],[]]
- Output:
- [[0,1,3],[0,2,3]]
- Explanation:
Two routes lead to junction 3: through junction 1 or through junction 2.
Example 2
- Input:
- graph = [[1],[2],[]]
- Output:
- [[0,1,2]]
- Explanation:
There is a single chain of roads 0 -> 1 -> 2.
Example 3
- Input:
- graph = [[1,2,3],[2,3],[3],[]]
- Output:
- [[0,1,2,3],[0,1,3],[0,2,3],[0,3]]
- Explanation:
Four routes: 0-1-2-3, 0-1-3, 0-2-3 and 0-3.
Constraints
- 1 ≤
n=graph.length≤ 8 - Every
graph[i][j]is a different junction fromi, lies between 0 and n - 1, and no junction appears twice ingraph[i]. - The graph is acyclic.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(2^n * n)
- Space
- O(n)