All Routes From the Entrance to the Exit
Implement allRoutes
You are given a directed graph with no cycles, described as an adjacency list: graph[u] holds every node you can reach in one step from node u. Find every route from node 0 (the entrance) to node n-1 (the exit).
Because the graph has no cycles, a depth-first search cannot loop; recording the route while you walk and undoing each step on the way back (backtracking) lists all routes.
Example 1:
Input: graph = [[1,2],[3,4],[3],[4],[]]
Output: [[0,1,3,4],[0,1,4],[0,2,3,4]]
Example 2:
Input: graph = [[1],[]]
Output: [[0,1]]
Example 3:
Input: graph = [[1],[],[]]
Output: []
+ 14 hidden test cases run on Submit.
Constraints:
- ●
2 ≤ n ≤ 8 nodes numbered 0 … n-1; the graph is directed and has no cycles - ●
graph[u] lists, in increasing order, every node v that has a one-way road u → v (adjacency-list form of the graph) - ●
The entrance is node 0 and the exit is node n-1 - ●
Return every route from node 0 to node n-1 (each route is the list of nodes visited); the order of the routes does not matter
graph =
[[1,2], [3,4], [3], [4], []]