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

Instead of using the swap approach that we used in [https://beaglehq.netlify.app/posts/leetcode/46-permutations/](Permutations 1), we’re going to use an element counting approach here.

We will use a counter to keep track of the number of occurrences of each element in nums.

Then, we will use a depth-first search (DFS) approach to build permutations by adding elements to a temporary buffer only if they are still available (i.e., their count is greater than zero).

After adding an element, we will decrement its count and continue the DFS. Once we reach a permutation of the same length as nums, we will add it to the result list. Finally, we will backtrack by incrementing the count of the last added element and removing it from the buffer.

Keep in mind that we don’t have the option to skip elements here since we want to use all elements in each permutation.

Solution in Python


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

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

            for num in counter:
                if counter[num]:
                    buffer.append(num)
                    counter[num] -= 1
                    dfs(buffer)
                    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.