Clean C++ code 32ms, with explanation


  • 0
    S
    class Solution {
    vector<vector<int>> result;
    void renew(int a, int b, vector<int> V);  
    // make the permutation from a-th number to b-th number
    
    public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        
        int N=nums.size();
        
        if(N){ renew(1, N, nums); }
        
        return result;
        
      }
    };
    
    void Solution::renew(int a, int b, vector<int> V){
    
    if(a==b) {result.push_back(V);}   // stop at the last number case, push it into result
    
    else{
        
        renew(a+1, b, V);                  // case1: keep the a-th number, permute the rest
        
        sort(V.begin()+a, V.end());    // a little trick here to avoid repeat in the result
        
        for(int k=a; k<=b-1; k++){
            
            if(V[k]!=V[k-1] && V[k]!=V[a-1] ){   //case2: avoid two repeat cases, and produce new permutation
                
                int temp;
                temp=V[k];
                V[k]=V[a-1];
                V[a-1]=temp;
                
                renew(a+1, b, V);
                
                temp=V[k];
                V[k]=V[a-1];
                V[a-1]=temp;
                
                
            }
            
        }
        
        
        
    }
    

    }


Log in to reply
 

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