Back to course home
0% completed
Vote For New Content
All Paths From Source to Target (medium)
Problem Statement
Given a directed acyclic graph (DAG) with nodes labeled from 0
to n - 1
, find all possible paths from node 0 to node n - 1 and return them in any order.
The graph is given as follows: graph[i]
is a list of all nodes you can visit from node i
.
Examples
Example 1
- Input:
graph = [[2,3],[3,4],[3,4],[4],[]]
- Expected Output:
[[0,2,3,4],[0,2,4],[0,3,4]]
- Justification: You can go from node
0
to4
via2
and3
or only2
or only3
.
Example 2
- Input:
graph = [[1,3,4],[2,4],[3],[],[2,3]]
- Expected Output:
[[0,1,4],[0,4]]
- Justification: You can go from node
0
to4
via 1 or directly.
Example 3
- Input:
graph = [[1,2,3],[2,3,4],[3,4],[],[3]]
- Expected Output:
[[0,1,2,4],[0,1,4],[0,2,4]]
- Justification: There are total
3
paths from node0
to4
.
Constraints:
- n == graph.length
- 2 <= n <= 15
- 0 <= graph[i][j] < n
- graph[i][j] != i (i.e., there will be no self-loops).
- All the elements of graph[i] are unique.
- The input graph is guaranteed to be a DAG.
Try it yourself
Try solving this question here:
Python3
Python3
. . . .
.....
.....
.....
Like the course? Get enrolled and start learning!
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible