Sharing my C++ implementation of this good article

  • 3


    I've found a good explanation on how to attack this problem at

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

    class Solution {
        vector<vector<int> > permuteUnique(vector<int> &num) {
            sort(num.begin(), num.end());
            vector<vector<int>> result;
            while (true){
                if (!nextLargePermutation(num)) break;
            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

    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

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

  • 0

    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.