797. All Paths From Source to Target
1. Description
Given a directed acyclic graph (DAG) of n 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 (i.e., there is a directed edge from node i to node graph[i][j]).
2. Example
Example 1
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Example 2
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
3. 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.
4. Solutions
Depth-First Search
n = graph.size()
Time complexity: O(n$2^n$)
Space complexity: O(n)
// In the worst case (a fully connected DAG where for any i < j there is an edge i -> j),
// each path from node 0 to node n-1 corresponds to choosing a subset of intermediate nodes.
// Thus, the number of paths is exponential (≈ 2^(n-2)), and copying each path costs O(n),
// leading to an overall time complexity of O(n * 2^n).
class Solution {
public:
vector<vector<int>> allPathsSourceTarget(const vector<vector<int>> &graph) {
vector<int> path{0};
vector<vector<int>> all_paths;
traverse(graph, path, all_paths);
return all_paths;
}
private:
void traverse(
const vector<vector<int>> &graph,
vector<int> &path,
vector<vector<int>> &all_paths) {
int current_node = path.back();
for (int i = 0; i < graph[current_node].size(); ++i) {
path.push_back(graph[current_node][i]);
if (path.back() == graph.size() - 1) {
all_paths.push_back(path);
} else {
traverse(graph, path, all_paths);
}
path.pop_back();
}
}
};