Q2 All Paths From Source to Target - LeetCode 797
Sat Apr 08 2023 16:13:47 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
/* we dont need visited in this question as input is provided uniquely*/
List<List<Integer>> psf = new ArrayList<>(); //paths so far
List<Integer> path = new ArrayList<>(); //current path
//adding current edge
path.add(0);
//graph , source , destination , visited , paths so far
dfs(graph, 0 , graph.length-1 ,psf , path);
return psf;
}
public void dfs(int[][] graph , int source , int destination ,List<List<Integer>>psf ,List<Integer> path ){
//adding path in the paths so far arraylist
if(source == destination){
psf.add(new ArrayList<>(path));
return;
}
for(int edge : graph[source]){
path.add(edge); //adding current edge in current path
//calling dfs for current edge
dfs(graph , edge , destination , psf , path);
//removing current edge as we explore different edges
path.remove(path.size() - 1);
}
return;
}
}
content_copyCOPY
https://leetcode.com/problems/all-paths-from-source-to-target/
Comments