C++ solution with next permutation


  • 0
    Y

    Get the idea from jianchao
    https://discuss.leetcode.com/topic/15219/easy-solution-using-code-in-nextpermutation

    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int>> reval;
            std::sort(nums.begin(),nums.end());
            reval.push_back(nums);
            while(nextPermutation(nums)){
                reval.push_back(nums);
            }
            return reval;
        }
    private:
        bool nextPermutation(vector<int>& nums){
            int vio_index(nums.size()-2);
            while(vio_index>=0 && nums[vio_index] >= nums[vio_index+1]){
                -- vio_index;
            }
            if(vio_index == -1) return false;
            std::reverse(nums.begin()+vio_index+1, nums.end());
            //find the upper bound value
            auto iter = std::upper_bound(nums.begin()+vio_index+1,nums.end(),nums[vio_index]);
            std::swap(nums[vio_index],*iter);
            return true;
        }
    };
    

Log in to reply
 

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