all-paths-from-source-to-targetV2.dart (1301B)
1 //Return a list of all possible paths that lead to the highest node starting from 0. 2 //The input list is a list of edges for each node thus a list of lists. 3 //The time complexity of this code is O(k^n) where n is the number of nodes and 4 //k is the number of edges per node (assuming an equal number of edges per node which is not given). 5 //This solution assumes that all nodes are in ascending order so the highest node's value will be 6 //graph.length - 1. 7 //Time: 361ms Beats: 50% 8 //Memory: 156.8MB Beats: 50% 9 10 class Solution { 11 List<List<int>> paths = []; 12 int highest_val = 0; 13 List<List<int>> graph = []; 14 List<List<int>> allPathsSourceTarget(List<List<int>> graph_in) { 15 graph = graph_in; 16 highest_val = graph.length - 1; 17 recurse([0]); 18 return paths; 19 } 20 21 void recurse(List<int> visited){ 22 print(visited); 23 if(visited[visited.length - 1] == highest_val){ 24 paths.add(visited); 25 return; 26 } 27 for(int i = 0 ; i < graph[visited[visited.length - 1]].length; ++i){ 28 if(visited.contains(graph[visited[visited.length - 1]][i]) == false){ 29 List<int> next_visited = List<int>.from(visited); 30 next_visited.add(graph[visited[visited.length - 1]][i]); 31 recurse(next_visited); 32 } 33 } 34 } 35 36 37 }