Unique Permutations

Problem

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

Input

• nums - Array of integers

Approach

The brute force approach is to generate all permutations of \(nums\) and store them into an array. After storing all of the permutations, delete the duplicate permutations. This is a \(O(n!)\) solution, with very expensive space usage.

The better solution is actually not far-fetched from the brute force approach: use a hash table to store new permutations. If we encounter a permutation that is already stored in the hash table, skip the adding of that permutation. This will prevent duplicate entries.

After we calculate all permutations, convert the hash table to an array.

The time complexity does not change, but the space complexity is improved by only storing unique permutations.

Solution

There is one caveat with Python here: Lists cannot be hashed. Lists cannot be hashed because they are mutable data structures. We also don't want to add a set into a set either, since we don't want to store hash tables into hash tables 😦. A good compromise is to convert the list objects into immutable tuple objects. An alternative solution is a string, but converting a list to a string will involve a .copy() operation which takes \(O(n)\) time, so this isn't the best choice.

    def permuteUnique(self, nums: 'List[int]') -> 'List[List[int]]':
        cache = set()

        def _generate(arr, x):
            if x >= len(nums):
                return

            for i in range(x, len(arr)):
                arr[i], arr[x] = arr[x], arr[i]
                perm = tuple(arr)
                if perm not in cache:
                    cache.add(perm)
                _generate(arr, x+1)
                arr[i], arr[x] = arr[x], arr[i]

        _generate(nums, 0)
        return [list(perm) for perm in cache]