leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

combination-sum.dart (1124B)

      1 //Given a list of values return all possible combinations
      2 //of the values that add up to the target.
      3 //To do this I used memoization, dp, and recursion
      4 //to search for each possible combination without repeating computations
      5 //Time: 563ms Beats: 5.55%
      6 //Memory: 177.3MB Beats: 5.56%
      7 class Solution {
      8   List<List<int>> return_vals = [];
      9   Set<String> checked = {};
     10   List<List<int>> combinationSum(List<int> candidates, int target) {
     11     find_combos(candidates, target, []);
     12     return return_vals;
     13   }
     14 
     15   void find_combos(List<int> canidates , int target, List<int> tried){
     16     String check_str = "";
     17     for(int i = 0 ; i < tried.length ; ++i){
     18       check_str += tried[i].toString() + " ";
     19     }
     20     if(checked.contains(check_str)){
     21       return;
     22     }
     23     checked.add(check_str);
     24     if(target < 0){
     25       return;
     26     }
     27     if(target == 0){
     28       return_vals.add(tried);
     29     }
     30     for(int i = 0 ; i < canidates.length ; ++i){
     31       List<int> new_tried = List.from(tried);
     32       new_tried.add(canidates[i]);
     33       new_tried.sort();
     34       find_combos(canidates , target - canidates[i] , new_tried);
     35     }
     36     return;
     37   }
     38 }