797. All Paths From Source to Target LeetCode Solution
In this guide, you will get 797. All Paths From Source to Target LeetCode Solution with the best time and space complexity. The solution to All Paths From Source to Target problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of All Paths From Source to Target
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]).
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.
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.
Complexity Analysis
Time Complexity: O(n \cdot 2^n)
Space Complexity: O(n \cdot 2^n)
797. All Paths From Source to Target LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> ans;
dfs(graph, 0, {0}, ans);
return ans;
}
private:
void dfs(const vector<vector<int>>& graph, int u, vector<int>&& path,
vector<vector<int>>& ans) {
if (u == graph.size() - 1) {
ans.push_back(path);
return;
}
for (const int v : graph[u]) {
path.push_back(v);
dfs(graph, v, std::move(path), ans);
path.pop_back();
}
}
}; /* code provided by PROGIEZ */
797. All Paths From Source to Target LeetCode Solution in Java
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> ans = new ArrayList<>();
dfs(graph, 0, new ArrayList<>(List.of(0)), ans);
return ans;
}
private void dfs(int[][] graph, int u, List<Integer> path, List<List<Integer>> ans) {
if (u == graph.length - 1) {
ans.add(new ArrayList<>(path));
return;
}
for (final int v : graph[u]) {
path.add(v);
dfs(graph, v, path, ans);
path.remove(path.size() - 1);
}
}
} // code provided by PROGIEZ
797. All Paths From Source to Target LeetCode Solution in Python
class Solution:
def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
ans = []
def dfs(u: int, path: list[int]) -> None:
if u == len(graph) - 1:
ans.append(path)
return
for v in graph[u]:
dfs(v, path + [v])
dfs(0, [0])
return ans # code by PROGIEZ
