combination-sum-ii.dart (1462B)
1 //Given a set of candidates return all unique combinations 2 //of candidates that add up to the target number. 3 //To do this I used recursion, dp, and memoization. 4 //I first checked to see if a certain set of numbers had already 5 //been checked. If yes then the branch ended if not then I added 6 //it to my memoized list and continued on. This ensures that no duplicates 7 //will be used. 8 //Time: 425ms Beats: 16.67% 9 //Memory: 175.9MB Beats: 33.33% 10 class Solution { 11 List<List<int>> combinationSum2(List<int> candidates, int target) { 12 return (allCombinations(candidates, target, [], {})); 13 } 14 List<List<int>> allCombinations(List<int> candidates, int target , List<int> previous, Set<String> memo){ 15 String current_str = ""; 16 previous.sort(); 17 for(int i = 0 ; i < previous.length ; ++i){ 18 current_str += previous[i].toString() + " "; 19 } 20 if(memo.contains(current_str)){ 21 return []; 22 } 23 memo.add(current_str); 24 if(target == 0){ 25 return [previous]; 26 } 27 if(target < 0){ 28 return []; 29 } 30 List<List<int>> return_list = []; 31 for(int i = 0 ; i < candidates.length ; ++i){ 32 List<int> prev = List.from(previous); 33 prev.add(candidates[i]); 34 List<List<int>> combo = allCombinations(candidates.sublist(i + 1) , target - candidates[i] , prev, memo); 35 for(int i = 0 ; i < combo.length ; ++i){ 36 return_list.add(combo[i]); 37 } 38 } 39 return return_list; 40 } 41 }