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]).
https://leetcode.com/problems/all-paths-from-source-to-target/description/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { public List<List<Integer>> allPathsSourceTarget(int[][] graph) { //final list of paths to return List<List<Integer>> paths = new ArrayList<>(); //to keep track of the current path List<Integer> path = new ArrayList<>(); //all the paths will be orginated from 0 path.add(0); dfs(graph, 0, 0, graph.length-1, path, paths); return paths; } private void dfs(int[][] graph, int src, int curr, int dest,List<Integer> path, List<List<Integer>> paths){ //check if the current node is the dest node //then add the path list to paths and return if(curr==dest){ paths.add(new ArrayList<>(path)); return; } //perform dfs on the adjacent nodes for(int node: graph[curr]){ path.add(node); dfs(graph, src, node, dest, path, paths); path.remove(path.size()-1); } } } |