Description
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]
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]]
Constraints:
1 <= nums.length <= 8-10 <= nums[i] <= 10
Solution
Python3
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
n = len(nums)
def backtrack(mask, path):
if len(path) == n:
res.append(path)
return
for i in range(n):
if mask & (1 << i) > 0: continue
if i > 0 and nums[i] == nums[i - 1] and mask & (1 << (i - 1)) > 0: continue
backtrack(mask | (1 << i), path + [nums[i]])
backtrack(0, [])
return res