leetcode

commit 30a918e9bbac48f4e0ec30ab537afe974ada0774
parent 7691cbf6e7e0b6de223124d8e37e332c6b249c7b
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun, 28 May 2023 17:08:27 -0500

Completed combination sum iii using dart, backtracking, and recursion

Diffstat:
A
combination-sum-iii/combination-sum-iii.dart
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 45 insertions(+), 0 deletions(-)
diff --git a/combination-sum-iii/combination-sum-iii.dart b/combination-sum-iii/combination-sum-iii.dart
@@ -0,0 +1,45 @@
+//Given a number k where k is the number of values to add together
+//and n is the target value return all combinations of numbers 1-9
+//that add up to n where no numbers 1-9 are used twice in the same
+//list, and no duplicate lists are returned. 
+//To do this I first created all of the options (1-9). I then
+//called a function that takes the number of values needed, the target number,
+//and the remaining options. For each iteration it tries to see if all options
+//create viable answers if they do that means that the length of the list
+//is k and the target = 0. Then the list is returned to the parent which adds on the value
+//that is recursed with moving up until reaching the top.
+
+//Note: In order to not return duplicate results I made
+//sure to use a sublist starting from the checked value that
+//way you will not remove just a single value and thus try 1 , 3 and 3 , 1 which would
+//return permutations not combinations.
+
+//Time: 263ms Beats: 100%
+//Memory: 141.6MB Beats: 100%
+class Solution {
+  List<List<int>> combinationSum3(int k, int n) {
+      List<int> opts = [];
+      for(int i = 1 ; i <= 9 ; ++i){
+          opts.add(i);
+      }
+      return combinations(opts, n , k);
+  }
+  List<List<int>> combinations(List<int> options , int target, int nums){
+      if(nums == 0){
+          if(target == 0){
+              return [[]];
+          }
+          return [];
+      }
+      List<List<int>> return_list = [];
+      for(int i = 0 ; i < options.length ; ++i){
+          List<int> opts_new = options.sublist(i + 1);
+          List<List<int>> combos = combinations(opts_new , target - options[i] , nums - 1);
+          for(int x = 0 ; x < combos.length ; ++x){
+              return_list.add(combos[x]);
+              return_list[return_list.length - 1].add(options[i]);
+          }
+      }
+      return return_list;
+  }
+}