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; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter