leetcode

commit 4b548a9a2b55bcc8e56b75a26c237fa79a9aa6a3
parent 0aa91d51e6609f209d57913761c2f1b45312c197
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Thu, 11 May 2023 17:59:57 -0500

Updated solution to be better

Diffstat:
A
all-paths-from-source-to-target/all-paths-from-source-to-targetV2.dart
 | 
37
+++++++++++++++++++++++++++++++++++++

1 file changed, 37 insertions(+), 0 deletions(-)
diff --git a/all-paths-from-source-to-target/all-paths-from-source-to-targetV2.dart b/all-paths-from-source-to-target/all-paths-from-source-to-targetV2.dart
@@ -0,0 +1,37 @@
+//Return a list of all possible paths that lead to the highest node starting from 0.
+//The input list is a list of edges for each node thus a list of lists.
+//The time complexity of this code is O(k^n) where n is the number of nodes and
+//k is the number of edges per node (assuming an equal number of edges per node which is not given).
+//This solution assumes that all nodes are in ascending order so the highest node's value will be
+//graph.length - 1.
+//Time: 361ms Beats: 50%
+//Memory: 156.8MB Beats: 50%
+
+class Solution {
+  List<List<int>> paths = [];
+  int highest_val = 0;
+  List<List<int>> graph = [];
+  List<List<int>> allPathsSourceTarget(List<List<int>> graph_in) {
+      graph = graph_in;
+      highest_val = graph.length - 1;
+      recurse([0]);
+      return paths;
+  }
+
+  void recurse(List<int> visited){
+      print(visited);
+      if(visited[visited.length - 1] == highest_val){
+          paths.add(visited);
+          return;
+      }
+      for(int i = 0 ; i < graph[visited[visited.length - 1]].length; ++i){
+          if(visited.contains(graph[visited[visited.length - 1]][i]) == false){
+            List<int> next_visited = List<int>.from(visited);
+            next_visited.add(graph[visited[visited.length - 1]][i]);
+            recurse(next_visited);
+          }
+      }
+  }
+
+
+}