LintCode: Unique Permutations

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example

For numbers [1,2,2] the unique permutations are:

[

    [1,2,2],

    [2,1,2],

    [2,2,1]

]

 
class Solution {
private:
   void swap(vector<int> &nums, int i, int j)
   {
      int t = nums[i];
      nums[i] = nums[j];
      nums[j] = t;
   }
   
   void helper(vector<int> &nums, int pos, vector<vector<int>> &output)
   {
       if (pos == nums.size()) {
           output.push_back(nums);
           return;
       }
       
       set<int> used;
       for(int i = pos; i < nums.size(); i++)
       {
          if (used.count(nums[i]) == 0)
          {
             used.insert(nums[i]);
             swap(nums, pos, i);
             helper(nums, pos+1, output);
             swap(nums, pos, i);            
          }
       }
   }
   
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        vector<vector<int>> output;
        
        sort(nums.begin(), nums.end());
        helper(nums, 0, output);
        
        return output;
    }
};


class Solution2 {
private:

   void helper(vector<int> &nums, vector<int>& candidate, int idx, vector<bool> &used, vector<vector<int>> &output)
   {
      if(idx == nums.size()) {
          output.push_back(candidate);
          return;
      }
       
       for(int i = 0; i < nums.size(); )
       {
           if (!used[i])
           {
              used[i] = true;
              candidate[idx] = nums[i];
              helper(nums, candidate, idx+1, used, output);
              used[i] = false;
              
              i++;
              while(i < nums.size() && nums[i] == nums[i-1])
                i++; 
           }
           else
             i++;
       }
   }
   
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        int n = nums.size();
        vector<vector<int>> output;
        vector<bool> used(n, false);
        vector<int> candidate(n);
        
        sort(nums.begin(), nums.end());
        helper(nums, candidate, 0, used, output);
        
        return output;
    }
};