3sum.dart (1325B)
1 //Find all permutations that add up to 0 using three values from the list. 2 //Return all unique permutations. The time compexity 3 //of this solution is O(n^3) because it has to iterate through 4 //the list three times for each value which is not very efficient. 5 //Time: TLE 6 //Memory: TLE 7 class Solution { 8 Set<String> set_strs = {}; 9 Set<int> first = {}; 10 List<List<int>> threeSum(List<int> nums) { 11 List<List<int>> all_perm = permutations(nums); 12 return all_perm; 13 } 14 15 List<List<int>> permutations(List<int> nums){ 16 List<List<int>> return_list = []; 17 for(int i = 0 ; i < nums.length ; ++i){ 18 if(first.contains(nums[i])){ 19 continue; 20 } 21 first.add(nums[i]); 22 for(int x = i + 1; x < nums.length ; ++x){ 23 for(int y = x + 1 ; y < nums.length ; ++y){ 24 int first = nums[i]; 25 int second = nums[x]; 26 int third = nums[y]; 27 if(first + second + third == 0){ 28 List<int> ret = [first , second , third]; 29 ret.sort(); 30 String ret_str = ret[0].toString() + " " + ret[1].toString() + " " + ret[2].toString(); 31 if(set_strs.contains(ret_str)){ 32 continue; 33 } 34 set_strs.add(ret_str); 35 return_list.add(ret); 36 } 37 } 38 } 39 } 40 return return_list; 41 } 42 }