Generate All Distinct Permutations of a List with Duplicate Values

Given a list of integers that may contain duplicate values, return every distinct ordering of all of its elements.

Function Signature

def distinct_permutations(nums: list[int]) -> list[list[int]]:

Rules

• A permutation uses every element of nums exactly once, in some order.
• Two permutations are the same if they are equal as sequences of values, even when they come from rearranging equal elements. Each distinct permutation appears exactly once in the result.
• Return the permutations sorted in ascending lexicographic order: compare two permutations element by element, and the first position where they differ decides which comes first.

Constraints

• 1 <= len(nums) <= 8
• -10 <= nums[i] <= 10
• The result has at most 40320 permutations, reached when all eight elements are distinct.

Examples

Example 1

• Input: nums = [1, 1, 2]
• Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
• Explanation: Swapping the two 1 values gives the same sequence, so there are three distinct permutations rather than six.

Example 2

• Input: nums = [0, -1, 0]
• Output: [[-1, 0, 0], [0, -1, 0], [0, 0, -1]]
• Explanation: The order of the input does not matter; the output is always in lexicographic order.

Example 3

• Input: nums = [7]
• Output: [[7]]

Unique Orderings of a Multiset

You are given a list of integers nums, which may contain repeated values. Produce every distinct arrangement of all of its elements.

An arrangement places every element of nums exactly once, in some order. Two arrangements count as the same when they are equal as sequences of values; rearranging equal elements does not create a new arrangement. Each distinct arrangement must appear exactly once in your result.

Output order. Return the arrangements sorted in ascending lexicographic order: compare two arrangements element by element, using numeric comparison, and the first position where they differ decides which one comes first. The first arrangement is therefore nums sorted in ascending order, and the last is nums sorted in descending order.

Implement distinct_permutations(nums), which returns a list of lists of integers.

Example 1

• Input: nums = [1, 1, 2]
• Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
• Swapping the two 1 values gives the same sequence, so there are three distinct arrangements rather than six.

Example 2

• Input: nums = [0, -1, 0]
• Output: [[-1, 0, 0], [0, -1, 0], [0, 0, -1]]
• The input order does not matter; the output is always in lexicographic order, and -1 sorts before 0.

Example 3

• Input: nums = [7]
• Output: [[7]]

Constraints

• 1 <= len(nums) <= 8
• -10 <= nums[i] <= 10
• The result has at most 40320 arrangements, reached when all eight elements are distinct.
• Every value fits in a 32-bit signed integer.

Hints

1. If you sort the input first, how can you generate arrangements so that they come out already in lexicographic order?
2. Generating all n! orderings and removing duplicates afterwards works, but consider a method that never produces the same sequence twice in the first place.
3. Given one arrangement, can you compute the smallest arrangement that is strictly larger than it, treating equal values as indistinguishable?

Approach

The reference sorts nums, records that sorted arrangement (the lexicographically smallest one), and then repeatedly applies the "next permutation" step until no larger arrangement exists.

The next-permutation step works on sequences, not on element identities: scan from the right for the first index i with arr[i] < arr[i + 1] (the strict comparison is what skips equal neighbours). If there is none, the array is in non-increasing order and is the largest arrangement, so generation stops. Otherwise scan from the right for the first index j with arr[j] > arr[i], swap arr[i] and arr[j], and reverse the suffix after i. This yields the smallest sequence strictly greater than the current one.

Because each step moves to the next strictly larger sequence, every distinct arrangement is produced exactly once and in ascending lexicographic order, so no deduplication or final sort is needed. The number of arrangements produced is the multinomial coefficient n! / (c1! * c2! * ...), where the c values are the counts of each distinct value.

• Time complexity: O(n * P), where P <= n! is the number of distinct arrangements (each step and each copy costs O(n))
• Space complexity: O(n * P) for the returned arrangements; O(n) auxiliary