#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
class Solution{
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
       vector<vector<int> > ans;
       if(num.size()==0)
           return ans;

       vector<int> _num = num;
       sort(_num.begin(),_num.end());

       vector<int> _beforeOne = _num;
       ans.push_back(_num);
       while(nextPermutation(_num))
       {
           if(_num != _beforeOne)
           {
               ans.push_back(_num);
               _beforeOne = _num;
           }
       }
       return ans;
    }
private:
    bool nextPermutation(vector<int> &num)
    {
        return next_permutation(num.begin(),num.end());
    }

    template<typename BidiIt>
    bool next_permutation(BidiIt first,BidiIt last)
    {
        const auto rfirst = reverse_iterator<BidiIt>(last);
        const auto rlast = reverse_iterator<BidiIt>(first);

        auto pivot = next(rfirst);
        while(pivot != rlast && *pivot >= *prev(pivot))
        {
            ++pivot;
        }
        
        //this is the last permute, or the next is the same as the begin one
        if(pivot == rlast)
        {
            reverse(rfirst,rlast);
            return false;
        }
        //find the first num great than pivot
        auto change = rfirst;
        while(*change<=*pivot)
            ++change;

        swap(*change,*pivot);
        reverse(rfirst,pivot);
        return true;
    }
};

int main()
{
    vector<int> num;
    num.push_back(1);
    num.push_back(1);
    num.push_back(2);
     
    Solution myS;
    myS.permute(num);
    return 0;
}