algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

permutations-ii.cpp (1075B)

      1 class Solution {
      2 public:
      3 
      4     vector<vector<int>> genPerms(unordered_map<int,int> options, vector<int> current) {
      5         if(options.size() == 0) {
      6             return vector<vector<int>> {current};
      7         }
      8         vector<vector<int>> result {};
      9         auto currentOption = options;
     10         for(auto option: currentOption) {
     11             bool erased = false;
     12             options[option.first] -= 1;
     13             current.push_back(option.first);
     14             if (options[option.first] <= 0) {
     15                 options.erase(option.first);
     16                 erased = true;
     17             }
     18             auto next = genPerms(options, current);
     19             for(auto ls: next) {
     20                 result.push_back(ls);
     21             }
     22             current.pop_back();
     23             options[option.first] += 1;
     24         }
     25 
     26         return result; 
     27 
     28     }
     29 
     30     vector<vector<int>> permuteUnique(vector<int>& nums) {
     31         unordered_map<int,int> fullMap {};
     32 
     33         for(auto num : nums) {
     34             fullMap[num] += 1;
     35         }
     36 
     37         return genPerms(fullMap, vector<int>{});        
     38     }
     39 };