leetcode

commit 6ec1cfdb822cf3e859a140a838fec9ec33101c35
parent bc610d0989ec313ab47100be997e4a9a28ea7c30
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Wed, 10 May 2023 15:06:46 -0500

Completed permutations problem using decision tree and recursion

Diffstat:
A
permutations/permutations.dart
 | 
28
++++++++++++++++++++++++++++

1 file changed, 28 insertions(+), 0 deletions(-)
diff --git a/permutations/permutations.dart b/permutations/permutations.dart
@@ -0,0 +1,28 @@
+//Find and return all possible permutations of a given set of integers
+//To do this I used recursion to create a decision tree that splits off each time
+//depending on how many integers in the list are unused.
+//The time complexity of this code is O(n!)
+//Time: 276ms Beats: 50%
+//Memory: 142.7MB Beats: 33.33%
+
+class Solution {
+  List<List<int>> return_list = [];
+  List<List<int>> permute(List<int> nums) {
+      recurse(nums, []);
+      return return_list;
+  }
+  void recurse(List<int> vals , List<int> current){
+      if(vals.length == 1){
+          current.add(vals[0]);
+          return_list.add(current);
+          return;
+      }
+      for(int i = 0 ; i < vals.length ; ++i){
+          List<int> original = List.from(vals);
+          List<int> curr = List.from(current);
+          curr.add(original[i]);
+          original.removeAt(i);
+          recurse(original, curr);
+      }
+  }
+}