47. Permutations II
You are given an integer array nums that may contain repeated values. Return every distinct ordering of its elements — each unique arrangement must appear exactly once, no matter how many ways it could be formed by swapping equal values.
Return the arrangements in ascending lexicographic order (compare element by element at the first differing position).
For example, [1, 1, 2] has 3! = 6 raw orderings but only 3 distinct ones: [1,1,2], [1,2,1], [2,1,1]. The challenge is producing each of those once without generating all six and de-duplicating afterward.
Example 1:
Input: nums = [1, 1, 2]
Output: [[1,1,2], [1,2,1], [2,1,1]]
Explanation: The two 1s are interchangeable, so only 3 of the 6 raw orderings are distinct.
Example 2:
Input: nums = [2, 2, 1, 1]
Output: [[1,1,2,2], [1,2,1,2], [1,2,2,1], [2,1,1,2], [2,1,2,1], [2,2,1,1]]
Explanation: Choosing positions for the two 1s among four slots gives C(4,2) = 6 distinct rows, listed smallest-first.
Constraints:
- 1 ≤ nums.length ≤ 8
- -10 ≤ nums[i] ≤ 10
Hints:
Generating all n! orderings and throwing them into a set works, but it does n! work even when almost everything is a duplicate. Aim to never build the same row twice.
Sort nums first. Duplicates are then adjacent, which makes them easy to police during the search.
In the backtracking loop, skip index i when nums[i] == nums[i-1] and index i-1 is currently unused: among equal values, only the leftmost available copy may start a branch. That one rule kills every duplicate subtree at its root.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 1, 2]
Expected output: [[1,1,2], [1,2,1], [2,1,1]]