C++ 32ms solution also works for Permutations I


  • 0
    G

    The solution of Next Permutation is used here. We sort nums first, then it will be our first permutation. Then we keep getting its next permutation until we reached the last permutation (the reverse of first permutation). As we get each permutation, add them to the return value.

    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int>> ret;
            // case with nums.size() <= 1 is also handled properly
            sort(nums.begin(), nums.end());
            ret.push_back(nums); // first permutation
            int i, j;
            while(1){
                // find nums[i-1] < nums[i]
                for (i=nums.size()-1; i>0; i--){
                    if (nums[i-1] < nums[i]){
                        break;
                    }
                }
                if (i==0){ // next permutation would be the first one again. it means we have got all permutations, ready to return
                    break;
                }
                // find nums[j] > nums[i-1], j >= i
                for (j=nums.size()-1; j>=i; j--){
                    if (nums[j] > nums[i-1]){
                        break;
                    }
                }
                // swap
                swap(nums[j], nums[i-1]);
                // sort
                sort(nums.begin()+i, nums.end());
                // now nums is a new permutation
                ret.push_back(nums);
            }
            return ret;
        }
    };

Log in to reply
 

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