Non-recursive version


  • 0
    X

    inspired by https://leetcode.com/problems/next-permutation/

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

Log in to reply
 

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