Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:


Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Difficulty: interview

Starter code:

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        

Solutions:
class Solution:
     def permuteUnique(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         if not nums:
             return []
         
         nums.sort()
         n = len(nums)
         res = [nums[:]]
         i = n-1
         while i > 0:
             if nums[i-1] < nums[i]:
                 j = n-1
                 while nums[j] <= nums[i-1]:
                     j -= 1
                 nums[i-1], nums[j] = nums[j], nums[i-1]
                 nums[i:] = sorted(nums[i:])
                 res.append(nums[:])
                 i = n-1
             else:
                 i -= 1
         
         return res
         
         
         


class Solution:
     def permuteUnique(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         def dfs(nums):
             if not nums:
                 return [[]]
             dic = set()
             new = []
             for i in range(len(nums)):
                 if nums[i] not in dic:
                     dic.add(nums[i])
                     new += [[nums[i]] + item for item in dfs(nums[: i] + nums[i + 1 :])]
             return new
         
         return dfs(nums)

class Solution:
     def permuteUnique(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         res=[]
         nums.sort()
         self.dfs(nums,[],res,[False] * len(nums))
         return res
     
     def dfs(self,nums,path,res,used):
         if len(path)==len(nums):
             res.append(path)
         else:
             for i in range(len(nums)):
                 if used[i] or (i>0 and nums[i] == nums[i-1] and not used[i-1]):
                     continue
                 used[i] = True
                 self.dfs(nums,path+[nums[i]],res,used)
                 used[i]=False

class Solution:
     def permuteUnique(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         res = []
         nums.sort()
         def swap(a, i, j):
             temp = a[i]
             a[i] = a[j]
             a[j] = temp
         
         def helper(index, path):
             if index == len(nums) - 1:
                 res.append(path.copy())
             for i in range(index, len(nums)):
                 if i != index and path[i] == path[index]:
                     continue
                 swap(path, index, i)
                 helper(index + 1, path.copy())
             
         helper(0, nums)
         return res