hardBacktrackingPure DSA~35 min
All Distinct Permutations of a Multiset
Generate every distinct ordering of a collection that may contain duplicate values, without emitting the same ordering twice.
Problem
Given a collection of numbers nums that might contain duplicates, return all unique permutations in any order.
Input
An integer array nums, possibly with duplicates.
Output
A list of all unique permutations.
Constraints
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
- Duplicates are possible.
Examples
Example 1
Input
nums = [1,1,2]
Output
[[1,1,2],[1,2,1],[2,1,1]]
The duplicate 1s collapse symmetric permutations.
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]]
With no duplicates, all 6 permutations appear.