class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) 
    {
        //sort num
        for(int i=0;i<num.size();i++)
            for(int j=i+1;j<num.size();j++)
                if(num[i]>num[j])
                {
                    int tmp=num[i];
                    num[i]=num[j];
                    num[j]=tmp;
                }
        
        vector<vector<int>> result;
        int v[num.size()];
        generate(result,num,v,0);
        return result;
    }
    void generate(vector<vector<int>>& result,vector<int> num,int* v,int vdep)
    {
        if(num.size()==0)
        {
            vector<int> newnum;
            for(int i=0;i<vdep;i++)
                newnum.push_back(v[i]);
            result.push_back(newnum);
            return;
        }
        int index=0;
        int size=num.size();
        while(index<size)
        {
            vector<int> newnum;
            for(int i=0;i<size;i++)
                if(i!=index)
                    newnum.push_back(num[i]);
            v[vdep]=num[index];
            generate(result,newnum,v,vdep+1);
            //next different num
            while(index+1<size && num[index+1]==num[index]) index++;
            index++;
        }
    }
};