47. Permutations II

https://leetcode.com/problems/permutations-ii/

Problem

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

• 1 <= nums.length <= 8

• -10 <= nums[i] <= 10

Solution

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> pers({nums});
        while (nextPermutation(nums)) {
            pers.push_back(nums);
        }
        return pers;
    }
    bool nextPermutation(vector<int>& nums) {
        if (nums.size() <= 1) return false;
        const int n = nums.size();
        for (int i = n - 1; i >= 1; --i) {
            if (nums[i - 1] >= nums[i]) continue; 
            const int j = i - 1;
            for (int k = n - 1; k > j; --k) {
                if (nums[j] >= nums[k]) continue; 
                int temp = nums[j];
                nums[j] = nums[k];
                nums[k] = temp;
                sort(nums.begin() + j + 1, nums.end());
                return true;
            }
        }
        return false;
    }
};