Generate all unique permutations of an array that may contain duplicate values.
Problem
Given an integer array nums that may contain duplicate values, return all distinct permutations of the array.
A permutation is an ordering of all elements. Two permutations are considered the same if they contain the same numbers in the same order.
Your task is to list every unique arrangement that can be formed using each element exactly once.
Input Format
- A single array of integers
nums.
Output Format
- Return a list of all unique permutations.
- The order of permutations in the result does not matter.
Constraints
- Each element must be used exactly once in every permutation.
- Duplicate input values may lead to repeated permutations unless handled carefully.
- The solution should avoid emitting duplicate arrangements.
Hints
- Sorting the array can make duplicate handling easier.
- During backtracking, skip a number when it would create the same permutation branch as a previous identical number at the same depth.
- Another valid approach is to track remaining counts of each distinct value.
Input Format
nums: integer array that may contain duplicates.
Output Format
- A 2D array containing every distinct permutation of
nums.
Constraints
- Use each element exactly once per permutation.
- Return only unique permutations.
- The result order is not important.
Example 1
Input
nums = [1,1,2]
Output
[[1,1,2],[1,2,1],[2,1,1]]
Explanation
There are 3 unique permutations. Although the input has two 1s, duplicate orderings are filtered out.
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]]
Explanation
All values are distinct, so every permutation of the three numbers is valid.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.