Sharing my C++ implementation of this good article


  • 3
    S

    Hello,

    I've found a good explanation on how to attack this problem at http://decomplexify.blogspot.com/2014/05/permutations.html

    The website has very good explanation but I don't know Java so I'm sharing my C++ implementation.

    class Solution {
    public:
        vector<vector<int> > permuteUnique(vector<int> &num) {
            sort(num.begin(), num.end());
            vector<vector<int>> result;
            result.push_back(num);
            while (true){
                if (!nextLargePermutation(num)) break;
                
                result.push_back(num);
            }
            return result;
        }
        
        bool nextLargePermutation(vector<int> &num){
            int i=num.size()-2;
            for (; i>=0 && num[i] >= num[i+1]; i--) {}
            
            if (i<0) return false;
            
            int j=num.size()-1;
            for (; j>i && num[j] <= num[i]; j--) {}
            
            swap(num[i], num[j]);
            sort(num.begin()+i+1, num.end());
            return true;
        }
    };
    

  • 0
    S

    One sentence description of the idea: sort the input array. this should be the (lexicographically) smallest permutation. We incrementally compute the next large permutation by swapping the pair* of elements in the current state of the array and sorting the array after the first of the swapped element.

    pair* : pair which would produce the smallest of the other permuations.


  • 0
    R

    good reuse of other problem, this is what we should learn from here. thanks!


  • 0
    S

    according to your idea, you could use stl next_permutation directly


Log in to reply
 

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