All Paths From Source to Target
Medium · Graphs · Backtracking · Depth-First Search · Breadth-First Search · Graph
Problem
You are given a directed acyclic graph with n nodes labeled 0 to n - 1. graph[i] lists every node you can reach from node i in one step.
Return every path from node 0 to node n - 1, each written as the list of nodes it visits, in order. The paths themselves may be returned in any order; return an empty list if there is none.
Examples
Input: graph = [[1,2,3],[3],[3],[]] Output: [[0,1,3],[0,2,3],[0,3]]
Node 0 reaches 3 directly, or through 1, or through 2.
Input: graph = [[1],[2],[]] Output: [[0,1,2]]
The graph is one chain, so there is one path.
Input: graph = [[2],[2],[]] Output: [[0,2]]
Node 1 has an edge to 2 but nothing reaches node 1, so it is on no path.
Constraints
- n == len(graph)
- 2 <= n <= 15
- 0 <= graph[i][j] < n
- graph[i][j] != i, and the entries of graph[i] are distinct
- The graph is acyclic
Approaches
- Baseline: breadth-first search over partial paths — time O(2^n · n), space O(2^n · n)
Follow-up
There can be exponentially many paths: in the complete DAG on n nodes every subset of the middle nodes gives one, 2^(n − 2) in all. If you only need how many paths there are, a DP over the nodes in topological order counts them in O(n + e) without listing any.
Related problems
Start free on Cariara · Coding problems · System design studio
