Problem Statement in English

You’re given an array of integers nums that may contain duplicates. Return all the possible unique permutations. You can return the answer in any order.

Approach

We make very minor alterations to the approach listed in 46. Permutations.

Also, if the the elements of the array were not distinct, in the backtracking approach we would add a check to skip duplicates by sorting the array first and then checking if the current element is the same as the previous one at the same level of recursion, while for the swapping approach we would use a set to keep track of the elements that have already been used at the current level of recursion.

For the swap approach, we can use a set to keep track of the elements that have already been used at the current level of recursion. This way, we can avoid generating duplicate permutations.

For the backtracking approach, we check if the current element is the same as the previous one at the same level of recursion. If it is, we skip it to avoid generating duplicate permutations.

An alternative approach is to use a counter to keep track of the number of occurrences of each element in the array. Then we iterate over the keys in the counter and use them to generate the unique permutations. It automatically ensures that we don’t reuse the same element at the same level of recursion, thus avoiding duplicates.

Solution in Python

  • Swap Approach

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

        def backtrack(level, arr):
            if level == l:
                res.append(arr.copy())
                return

            # Track values swapped at the current depth to skip duplicate branches
            seen = set()

            for i in range(level, l):
                if arr[i] in seen:
                    continue

                seen.add(arr[i])

                # Swap
                arr[level], arr[i] = arr[i], arr[level]

                # Recurse for next position
                backtrack(level + 1, arr)

                # Backtrack / Swap back
                arr[level], arr[i] = arr[i], arr[level]

        backtrack(0, nums)
        return res
  • Backtracking Approach

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # Step 1: Sort to group duplicates together
        res = []
        buffer = []
        used = [False] * len(nums)

        def dfs():
            if len(buffer) == len(nums):
                res.append(buffer.copy())
                return

            for i in range(len(nums)):
                if used[i]:
                    continue
                
                # Step 2: Skip identical elements at the same depth level
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue

                used[i] = True
                buffer.append(nums[i])

                dfs()

                buffer.pop()
                used[i] = False

        dfs()
        return res
  • Counter Approach

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        counter = Counter(nums)
        res = []
        buffer = []

        def dfs():
            if len(buffer) == len(nums):
                res.append(buffer.copy())
                return

            for num in counter:
                if counter[num]:
                    buffer.append(num)
                    counter[num] -= 1

                    dfs()

                    counter[num] += 1
                    buffer.pop()
            
        dfs()
        return res

Complexity

  • Time: $O(n \times n!)$
    Since there are $n!$ unique permutations and generating each permutation takes $O(n)$ time.

  • Space: $O(n \times n!)$
    Since we are storing all the unique permutations.

Mistakes I Made

I had a hard time trying to do this with the swap approach. It got really complicated trying to avoid duplicates while swapping elements.

And we are done.