Using recursive way, but seems slow


  • 0
    P
    typedef vector<int> vi;
    vector<vi> generate(vi a,int m){
        vector<vi> per;
        if(m==1){
            per.push_back(vi{a[0]});
            return per;
        }
        unordered_set<int> used;
        for(int j=m-1;j>=0;j--){
            if(used.find(a[j])!=used.end()) continue;
            used.insert(a[j]);
            if(j!=m-1) swap(a[j],a[m-1]);
            vector<vi> tmp = generate(a,m-1);
            for(vi vec:tmp){
                vec.push_back(a[m-1]);
                per.push_back(vec);
            }
        }
        return per;
    }
    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            return generate(nums,nums.size());
        }
    };

  • 0
    P

    Another

    typedef vector<int> vi;
    bool next_per(vi & a){
        int i,j;
        for(j=a.size()-1;j>0&&a[j]<=a[j-1];j--);
        if(j==0) return false;
        for(i=a.size()-1;a[i]<=a[j-1];i--);
        swap(a[i],a[j-1]);
        for(i=0;i<(a.size()-j)/2;i++) swap(a[j+i],a[a.size()-1-i]);
        return true;
        
    }
    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vi> per;
            sort(nums.begin(),nums.end());
            do{
                per.push_back(nums);
            }while(next_per(nums));
            return per;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.