Description:

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]
]

Solution:

class Solution:
    def permuteUnique(self, nums: List[int], sort = False) -> List[List[int]]:
        if len(nums) < 2:
            return [nums]
        
        if sort == False:
            nums.sort()
            
        result = []
        
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            cache_start = [nums[i]]
            for cache_follow in self.permuteUnique(nums[:i]+nums[i+1:],True):
                result.append(cache_start + cache_follow)
                
        return result

Performance:

• Runtime: 68 ms, faster than 94.08% of Python3 online submissions for Permutations II.
• Memory Usage: 13.3 MB, less than 81.64% of Python3 online submissions for Permutations II.