Easy solution using code in nextPermutation


  • 14

    Well, have you solved the Next Permutation problem? If so and you have handled the cases of duplicates at that problem, your code can be used in this problem. The idea is fairly simple:

    1. sort nums in ascending order, add it to res;
    2. generate the next permutation of nums using nextPermutation(), and add it to res;
    3. repeat 2 until the next permutation of nums returns to the sorted condition in 1.

    The code is as follows. For more about the idea of nextPermutation(), please visit this solution.

        bool nextPermutation(vector<int>& nums) { 
            int k = -1;
            for (int i = nums.size() - 2; i >= 0; i--) {
                if (nums[i] < nums[i + 1]) {
                    k = i;
                    break;
                }
            }
            if (k == -1) {
                sort(nums.begin(), nums.end());
                return false;
            }
            int l = -1;
            for (int i = nums.size() - 1; i > k; i--) {
                if (nums[i] > nums[k]) {
                    l = i;
                    break;
                }
            }
            swap(nums[k], nums[l]);
            reverse(nums.begin() + k + 1, nums.end());
            return true;
        }
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int> > res;
            sort(nums.begin(), nums.end());
            res.push_back(nums);
            while (nextPermutation(nums))
                res.push_back(nums);
            return res;
        }
    

  • 0
    N

    Same logic without using sort and reverse function

        bool next_permutation(vector<int>& nums)
        {
            int i=0, j=nums.size()-1;
            
            while(j>0 && nums[j]<=nums[j-1])
                j--;
            if(j==0)
                return false;
            int m=j,n=nums.size()-1;
            j--;
            while(m<n)
            {
                swap(nums[m++],nums[n--]);
            }
            int k=j+1;
            
            while(k<nums.size() && nums[k]<=nums[j])
                k++;
            if(k<nums.size())
                swap(nums[k],nums[j]);
            return true;
        }
        
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int>> res;
            sort(nums.begin(),nums.end());
            res.push_back(nums);
            while(next_permutation(nums))
                res.push_back(nums);
            
            return res;
        }

  • 0

    Java version I wrote on my own, which is super slow... Definitely not recommended.

    Maybe the conversion process from array to list makes it so slow.

    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList();
            List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
            res.add(list);
            while (permuteNext(nums)) {
                List<Integer> list1 = Arrays.stream(nums).boxed().collect(Collectors.toList());
                res.add(list1);
            }
            return res;
        }
        
        private boolean permuteNext(int[] nums) {
            int n = nums.length;
            int k = n - 1, l = n - 1;
            while (k > 0 && nums[k] <= nums[k - 1]) 
                k--;
            if (--k < 0) {
                reverse(nums, 0, n - 1);
                return false;
            }
            while (l > k && nums[l] < nums[k]) 
                l--;
            nums[k] ^= nums[l];
            nums[l] ^= nums[k];
            nums[k] ^= nums[l];
            reverse(nums, k + 1, n - 1);
            return true;
        }
        
        private void reverse(int[] nums, int start, int end) {
            while (start < end) {
                nums[start] ^= nums[end];
                nums[end] ^= nums[start];
                nums[start] ^= nums[end];
                start++;
                end--;
            }
        }
    }
    

Log in to reply
 

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