C++ solution based on next permutation STL


  • 0
    M

    Algorithm:

    1. Arrange the elements in ascending order.
    2. To get the next perm, start from index size-1 and search for first ascending order pair.
    3. swap the value with next highest number looking from the end occurring after i-1.
    4. Due to swap, the order is disturbed, so restore the ascending order by reversing elements from next index.
     class Solution {
            public:
                vector<vector<int> > permuteUnique(vector<int> &num) {
                    if(num.size() <=1)
                    {
                    	res.push_back(num);
                    	return res;
                    }
                    //Put the elements in ascending order
                    sort(num.begin(), num.end());       
                    res.push_back(num);
                    int i,j;
                    while (1){
                    	//Find if there is any strict asc order at i-1
                    	i = num.size()-1;
                    	while(i and num[i-1] >= num[i])
                    		i--; 
                    	
                        //No asc order found; Done with all perm
                        if(i == 0)
                            return res;
                        
            			//Find nextHighestValue after i-1 
            			j = num.size()-1;
                    	while(j>i-1 and num[i-1] >= num[j])
                    		j--;
                    	
                        //Move the NextHighestValue to i-1                   
                        swap(num[i-1], num[j]);
                        
                        //Restore the order from i to end: Desc to Asc
                        j = num.size()-1;
                        while(i<j)
                        {
                        	swap(num[i], num[j]);
                        	i++;j--;
                        }
                        res.push_back(num);
                    }
                    return res;
                }
            
                vector<vector<int> > res;
            };

Log in to reply
 

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