leetcode

commit 1c99e5756e5dbda6374f3746deb22d8b83c38e29
parent 4bf12792762ecf13cf7efe53ef128dd0f729960e
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun,  4 Jun 2023 17:30:47 -0500

Completed subsets ii using dart, recursion, and backtracking

Diffstat:
A
subsets-ii/subsets-ii.dart
 | 
35
+++++++++++++++++++++++++++++++++++

1 file changed, 35 insertions(+), 0 deletions(-)
diff --git a/subsets-ii/subsets-ii.dart b/subsets-ii/subsets-ii.dart
@@ -0,0 +1,35 @@
+//Return all subsets of numbers in the nums list where nums
+//contains duplicate values
+
+//To solve this I used recursion to go through all possible permutations
+//of the numbers list. If it was new then I added it's string representation to 
+//a set. If it was not the recursion ended with a null value returned.
+
+//Time: 275ms Beats: 57.14%
+//Memory: 143.5MB Beats: 14.29%
+class Solution {
+  List<List<int>> subsetsWithDup(List<int> nums) {
+      nums.sort();
+      return allSubsets(nums,[], {});
+  }
+  List<List<int>> allSubsets(List<int> nums, List<int> current, Set<String> used){
+      String curr = current.toString();
+      if(used.contains(curr)){
+          return [];
+      }
+      used.add(curr);
+      List<List<int>> return_list = [];
+      for(int i = 0 ; i < nums.length ; ++i){
+          List<int> new_nums = nums.sublist(i + 1);
+          int currint = nums[i];
+          List<int> new_curr = List.from(current);
+          new_curr.add(currint);
+          List<List<int>> output = allSubsets(List.from(new_nums), new_curr, used);
+          for(List<int> out in output){
+              return_list.add(out);
+          }
+      }
+      return_list.add(current);
+      return return_list;
+  }
+}