A non-recursive C++ implementation with O(1) space cost


  • 46
    T
    class Solution {
    public:
    	vector<vector<int> > permuteUnique(vector<int> &S) {
    		// res.clear();
    		sort(S.begin(), S.end());		
    		res.push_back(S);
    		int j;
    		int i = S.size()-1;
    		while (1){
    			for (i=S.size()-1; i>0; i--){
    				if (S[i-1]< S[i]){
    					break;
    				}
    			}
    			if(i == 0){
    				break;
    			}
    
    			for (j=S.size()-1; j>i-1; j--){
    				if (S[j]>S[i-1]){
    					break;
    				}
    			}					
    			swap(S[i-1], S[j]);
    			reverse(S, i, S.size()-1);
    			res.push_back(S);
    		}
    		return res;
        }
    	void reverse(vector<int> &S, int s, int e){		
    		while (s<e){
    			swap(S[s++], S[e--]);
    		}
    	}
    	
    	vector<vector<int> > res;
    };
    

    Basically, assume we have "1234", the idea is to increase the number in ascending order, so next is "1243", next is "1324", and so on.


  • 3
    T

    So you actually use O(1) space, if you just need to print out the permutations.


  • 0
    N
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 9
    W

    yes,you are right.Actually,it is a problem similar to "Next Permutation", which rearranges numbers into the lexicographically next greater permutation of numbers. the difference between these two problems lies in how permutations we are required to generate.sorry,my English level is limited,hope this might help.

      bool nextPermutation(vector<int> &num) {
        	int len=num.size()-1;
        	for(int pos=len-1;pos>=0;--pos){
        		if(num[pos]<num[pos+1]){
        			int smallNum=num[pos];
        			int lastPosBiggerThanSmallNum=
        				len-(find_if(num.rbegin(),
        				num.rend(),(bind2nd(greater<int>(),smallNum)))-		
        				num.rbegin());
        			swap(num[pos],num[lastPosBiggerThanSmallNum]);
        			sort(num.begin()+pos+1,num.end());
        			return true;
        		}
        	}
        	return false;
        }
        vector<vector<int> > permuteUnique(vector<int> &num){
        	vector<vector<int> > res;
        	if(num.empty())	
        		return res;
        	sort(num.begin(),num.end());
        	res.push_back(num);
        	while(nextPermutation(num)){
        		res.push_back(num);
        	}
        	return res;
        }

  • 0
    S

    get next permutation each time!


  • 0
    W

    Is it possible that we do this without sorting the array?


  • 0
    M

    is the complexity O(n!*n)?


  • 0
    S

    I think it is O((n+1)!)


Log in to reply
 

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