47. Permutations II - Explanation

Description

You are given an array nums, that might contain duplicates , return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]

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

Example 2:

Input: nums= [2,2]

Output: [[2,2]]

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Backtracking (Hash Set)

Intuition

Since the input array may contain duplicates, generating all permutations naively would produce duplicate results. One straightforward way to handle this is to generate all permutations using standard backtracking and store them in a hash set, which automatically filters out duplicates.

We mark elements as "used" by temporarily replacing them with a sentinel value, ensuring each element is used exactly once per permutation.

Algorithm

Initialize an empty set to store unique permutations.
Use backtracking to build permutations:
- If the current permutation has the same length as nums, add it to the set.
- Otherwise, iterate through nums and for each unused element:
  - Mark it as used (replace with sentinel value).
  - Add it to the current permutation and recurse.
  - Restore the original value and remove it from the permutation.
Return all unique permutations from the set.

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

        def backtrack(perm):
            if len(perm) == len(nums):
                res.add(tuple(perm))
                return

            for i in range(len(nums)):
                if nums[i] != float("-inf"):
                    perm.append(nums[i])
                    nums[i] = float("-inf")
                    backtrack(perm)
                    nums[i] = perm[-1]
                    perm.pop()

        backtrack([])
        return list(res)

Time & Space Complexity

Time complexity: $O(n! * n)$
Space complexity: $O(n! * n)$ for the hash set.

2. Backtracking (Hash Map)

Intuition

Instead of using a set to filter duplicates after the fact, we can prevent duplicates from being generated in the first place. By counting how many times each unique number appears, we only pick each distinct value once per position in the permutation.

When we decrement a count to zero, that number is no longer available for deeper recursion levels. This naturally avoids generating the same permutation multiple times.

Algorithm

Build a frequency map counting occurrences of each number in nums.
Use backtracking to build permutations:
- If the current permutation has the same length as nums, add a copy to the result.
- Otherwise, iterate through each unique number in the frequency map:
  - If its count is greater than 0, add it to the permutation and decrement the count.
  - Recurse to fill the next position.
  - Increment the count back and remove the number from the permutation.
Return all permutations.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        perm = []
        count = {n: 0 for n in nums}
        for num in nums:
            count[num] += 1

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

            for num in count:
                if count[num] > 0:
                    perm.append(num)
                    count[num] -= 1
                    dfs()
                    count[num] += 1
                    perm.pop()

        dfs()
        return res

Time & Space Complexity

Time complexity: $O(n! * n)$
Space complexity: $O(n! * n)$ for the output list.

3. Backtracking (Boolean Array)

Intuition

By sorting the array first, duplicate values become adjacent. This allows us to apply a simple rule: when we encounter a duplicate, only use it if the previous identical element has already been used in the current permutation path. This ensures each unique arrangement is generated exactly once.

A boolean array tracks which indices are currently in use during backtracking.

Algorithm

Sort nums so duplicates are adjacent.
Create a boolean array visit to track used indices.
Use backtracking to build permutations:
- If the current permutation has the same length as nums, add a copy to the result.
- Otherwise, iterate through each index:
  - Skip if already visited.
  - Skip if this element equals the previous one and the previous one is not visited (to avoid duplicates).
  - Mark the index as visited, add the element to the permutation, and recurse.
  - Unmark the index and remove the element from the permutation.
Return all permutations.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res, n = [], len(nums)
        visit = [False] * n
        perm = []

        def dfs():
            if len(perm) == n:
                res.append(perm.copy())
                return

            for i in range(n):
                if visit[i]:
                    continue

                if i and nums[i] == nums[i - 1] and not visit[i - 1]:
                    continue
                visit[i] = True
                perm.append(nums[i])
                dfs()
                visit[i] = False
                perm.pop()

        nums.sort()
        dfs()
        return res

Time & Space Complexity

Time complexity: $O(n! * n)$
Space complexity: $O(n! * n)$ for the output list.

4. Backtracking (Optimal)

Intuition

This approach generates permutations by swapping elements in place rather than building a separate permutation array. At each position i, we try placing each element from index i onward. By sorting first and skipping swaps that would place a duplicate value at position i, we avoid generating duplicate permutations.

After each recursive call, we restore the array to its sorted state for position i by reverse-swapping all elements back.

Algorithm

Sort nums so duplicates are adjacent.
Use backtracking starting at index 0:
- If index i equals the length of nums, add a copy of nums to the result.
- Otherwise, for each index j from i to the end:
  - Skip if j > i and nums[j] equals nums[i] (duplicate at this position).
  - Swap nums[i] and nums[j], then recurse with i + 1.
- After the loop, restore the array by reverse-swapping elements back from the end to i + 1.
Return all permutations.

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

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

            for j in range(i, len(nums)):
                if j > i and nums[i] == nums[j]:
                    continue

                nums[i], nums[j] = nums[j], nums[i]
                dfs(i + 1)

            for j in range(len(nums) - 1, i, -1):
                nums[j], nums[i] = nums[i], nums[j]

        nums.sort()
        dfs(0)
        return res

Time & Space Complexity

Time complexity: $O(n! * n)$
Space complexity: $O(n! * n)$ for the output list.

5. Iteration

Intuition

This approach uses the "next permutation" algorithm to iterate through all permutations in lexicographic order. Starting from the smallest permutation (sorted array), we repeatedly find the next lexicographically larger permutation until we cycle back to the beginning.

Since we generate permutations in strict order, duplicates in the input naturally produce unique permutations without extra handling.

Algorithm

Sort nums to get the lexicographically smallest permutation.
Add a copy of nums to the result.
Repeat until we return to the starting permutation:
- Find the largest index i such that nums[i] < nums[i + 1]. If no such index exists, we have the last permutation.
- Find the largest index j such that nums[j] > nums[i].
- Swap nums[i] and nums[j].
- Reverse the subarray from i + 1 to the end.
- Add a copy of nums to the result.
Return all permutations.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        res = [nums.copy()]

        while True:
            i = n - 2
            while i >= 0 and nums[i] >= nums[i + 1]:
                i -= 1

            if i < 0:
                break

            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

            l, r = i + 1, n - 1
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l, r = l + 1, r - 1

            res.append(nums.copy())

        return res

Time & Space Complexity

Time complexity: $O(n! * n)$
Space complexity: $O(n! * n)$ for the output list.

Common Pitfalls

Forgetting to Sort the Array

When using the boolean array approach to skip duplicates, the array must be sorted first so that duplicate values are adjacent. Without sorting, the condition nums[i] == nums[i-1] does not correctly identify duplicates, and the algorithm produces duplicate permutations.

Incorrect Duplicate Skipping Logic

The condition to skip duplicates is subtle: skip when i > 0 && nums[i] == nums[i-1] && !visit[i-1]. Mistakenly using visit[i-1] instead of !visit[i-1] (or vice versa) still produces correct results but may generate duplicates or miss valid permutations. Understanding why we check if the previous duplicate was NOT used is key to correctness.

Using Wrong Sentinel Values

When marking elements as "used" with a sentinel value (like Integer.MIN_VALUE or -Infinity), ensure the sentinel cannot appear as a valid input value. If the input can contain the sentinel value, the algorithm incorrectly skips valid elements or includes already-used elements.