leetcode

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

permutations-ii.dart (1983B)

      1 //Find all permutations of a list of nums ensuring that
      2 //duplicate permutations are not returned despite the fact
      3 //that there may be duplicate values in the nums list.
      4 //To solve this I first found every permutation then iterated through that
      5 //list of permutations comparing the lists with existing lists in the return to verify
      6 //they were unique. This is not super fast, but it does work better than any other solution
      7 //I could think of.
      8 //Time: 1183ms Beats: 11.11%
      9 //Memory: 206.9MB Beats: 11.11%
     10 
     11 class Solution {
     12   List<List<int>> permuteUnique(List<int> nums) {
     13       List<List<int>> return_list = allPerms(nums);
     14       List<List<int>> return_ls = [];
     15       int itr = 0;
     16       for(List<int> list in return_list){
     17           bool dupe = false;
     18           for(int i = itr + 1 ; i < return_list.length ; ++i){
     19               if(equal_lists(list , return_list[i])){
     20                   dupe = true;
     21                   break;
     22               }
     23           }
     24           if(!dupe){
     25             return_ls.add(list);
     26           }
     27           itr += 1;
     28       }
     29       return return_ls;
     30   }
     31 
     32 
     33   bool equal_lists(List<int> list_one , List<int> list_two){
     34       if(list_one.length != list_two.length){
     35           return false;
     36       }
     37       for(int i = 0 ; i < list_one.length ; ++i){
     38           if(list_one[i] != list_two[i]){
     39               return false;
     40           }
     41       }
     42       return true;
     43   }
     44 
     45 
     46 
     47     List<List<int>> allPerms(List<int> nums) {
     48       List<List<int>> return_list = [];
     49       if(nums.length == 1){
     50           return [[nums[0]]];
     51       }
     52       for(int i = 0 ; i < nums.length ; ++i){
     53           List<int> new_nums = List.from(nums);
     54           int removed_val = new_nums[i];
     55           new_nums.removeAt(i);
     56           List<List<int>> returned_list = allPerms(new_nums);
     57           for(int x = 0 ; x < returned_list.length ; ++x){
     58              returned_list[x].add(removed_val);
     59              return_list.add(returned_list[x]);
     60           }
     61           
     62       }
     63       return return_list;
     64   }
     65 }