Permutations II

How it works

This approach uses the "next permutation" algorithm to iterate through all permutations in lexicographic order. Starting from the smallest permutation (sorted array), we repeatedly find the next lexicographically larger permutation until we cycle back to the beginning.

Since we generate permutations in strict order, duplicates in the input naturally produce unique permutations without extra handling.

Steps

1. Sort nums to get the lexicographically smallest permutation.
2. Add a copy of nums to the result.
3. Repeat until we return to the starting permutation:
   • Find the largest index i such that nums[i] < nums[i + 1]. If no such index exists, we have the last permutation.
   • Find the largest index j such that nums[j] > nums[i].
   • Swap nums[i] and nums[j].
   • Reverse the subarray from i + 1 to the end.
   • Add a copy of nums to the result.
4. Return all permutations.

Complexity

• Time complexity: O(n! * n)
• Space complexity: O(n! * n) for the output list.

Things to watch for

Forgetting to Sort the Array

When using the boolean array approach to skip duplicates, the array must be sorted first so that duplicate values are adjacent. Without sorting, the condition nums[i] == nums[i-1] does not correctly identify duplicates, and the algorithm produces duplicate permutations.

Incorrect Duplicate Skipping Logic

The condition to skip duplicates is subtle: skip when i > 0 && nums[i] == nums[i-1] && !visit[i-1]. Mistakenly using visit[i-1] instead of !visit[i-1] (or vice versa) still produces correct results but may generate duplicates or miss valid permutations. Understanding why we check if the previous duplicate was NOT used is key to correctness.

Using Wrong Sentinel Values

When marking elements as "used" with a sentinel value (like Integer.MIN_VALUE or -Infinity), ensure the sentinel cannot appear as a valid input value. If the input can contain the sentinel value, the algorithm incorrectly skips valid elements or includes already-used elements.

from typing import List

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        res = [nums.copy()]

        while True:
            i = n - 2
            while i >= 0 and nums[i] >= nums[i + 1]:
                i -= 1

            if i < 0:
                break

            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

            l, r = i + 1, n - 1
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l, r = l + 1, r - 1

            res.append(nums.copy())

        return res

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> res = {nums};

        while (true) {
            int i = n - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) i--;

            if (i < 0) break;

            int j = n - 1;
            while (nums[j] <= nums[i]) j--;

            swap(nums[i], nums[j]);
            reverse(nums.begin() + i + 1, nums.end());
            res.push_back(nums);
        }

        return res;
    }
};