Problem Description

You are given a collection of numbers nums that might contain duplicates. Your task is to return all possible unique permutations of these numbers. The permutations can be returned in any order.

A permutation is a rearrangement of all the elements in the collection. Since the input may contain duplicate numbers, you need to ensure that duplicate permutations are not included in your result.

For example:

• If nums = [1,1,2], the unique permutations would be [[1,1,2], [1,2,1], [2,1,1]]
• Notice that even though there are two 1s in the input, we don't include duplicate permutations like having [1,1,2] appear twice in our result

The key challenge here is handling the duplicate elements properly to avoid generating the same permutation multiple times while still ensuring all unique permutations are generated.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves generating permutations of an array, not traversing nodes and edges in a graph structure.

Need to solve for kth smallest/largest?

• No: We need to generate all unique permutations, not find a specific kth element.

Involves Linked Lists?

• No: The problem works with an array/list of numbers, not linked list data structures.

Does the problem have small constraints?

• Yes: Generating permutations has factorial time complexity (n!), which means the problem typically has small constraints. For n elements, there are at most n! permutations, which grows extremely fast (e.g., 10! = 3,628,800), so practical problems usually have n ≤ 10-12.

Brute force / Backtracking?

• Yes: This is the perfect fit! We need to systematically explore all possible arrangements of the numbers, making choices at each position, and backtracking when we've completed a permutation or need to try a different choice. The backtracking approach allows us to:
  • Build permutations incrementally
  • Skip duplicate permutations by careful pruning
  • Explore all valid possibilities systematically

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This makes sense because we need to generate all possible unique arrangements while handling duplicates, which requires systematic exploration with the ability to undo choices (backtrack) and try alternatives.

Intuition

When we need to generate all unique permutations with possible duplicates, we face two main challenges: generating all permutations and avoiding duplicates.

Let's think about how we build permutations manually. We pick one element for the first position, then pick another for the second position from the remaining elements, and so on. This naturally suggests a recursive approach where at each step, we decide which element to place at the current position.

The key insight for handling duplicates comes from recognizing that duplicate permutations arise when we place identical elements in the same position across different recursive branches. For example, if we have [1, 1, 2] and we're filling the first position, placing the first 1 or the second 1 there would lead to the same set of permutations.

To avoid this, we can sort the array first, bringing duplicate elements together. Then, when choosing an element for a position, we skip over duplicates that haven't been used yet in the current path. The crucial observation is: if we haven't used nums[j-1] (the previous duplicate), we shouldn't use nums[j] either, because this would create the same permutation that would be generated when nums[j-1] is chosen first.

The backtracking pattern fits perfectly here because:

1. We need to explore all possible choices systematically
2. After placing an element at position i, we recursively fill position i+1
3. We need to "undo" our choice (backtrack) to try other elements at the same position
4. We maintain a visited array to track which elements are currently being used in our permutation path

By combining sorting with a careful duplicate-skipping condition (j > 0 && nums[j] == nums[j-1] && !vis[j-1]), we ensure each unique permutation is generated exactly once. This condition says: "Skip this element if it's the same as the previous one and the previous one hasn't been used yet in the current permutation being built."

Learn more about Backtracking and Sorting patterns.

Solution Approach

The implementation uses sorting combined with backtracking to generate all unique permutations efficiently.

Step 1: Sort the array We start by sorting nums to group duplicate elements together. This is crucial for our duplicate-skipping logic to work correctly.

Step 2: Initialize data structures

• ans: Stores all unique permutations
• t: A temporary array of size n to build the current permutation
• vis: A boolean array to track which elements from nums are currently used in the permutation being built

Step 3: The DFS function The core logic is in the dfs(i) function, which fills the i-th position of the current permutation:

1. Base case: When i == n, we've filled all positions. We add a copy of the current permutation t to our answer list.

2. Recursive case: For each position i, we try every element nums[j] where j ranges from 0 to n-1:

   • Skip condition 1: If vis[j] is True, element nums[j] is already used in the current permutation, so skip it.

   • Skip condition 2: The critical duplicate-avoiding condition:

     j > 0 and nums[j] == nums[j-1] and not vis[j-1]

     This means: if the current element equals the previous element AND the previous element hasn't been used, skip the current element. This ensures we only use duplicates in a fixed order (always use the first occurrence before the second).

3. Make choice: If both conditions pass:

   • Place nums[j] at position i: t[i] = nums[j]
   • Mark it as used: vis[j] = True
   • Recursively fill the next position: dfs(i + 1)

4. Backtrack: After exploring all permutations with nums[j] at position i:

   • Unmark the element: vis[j] = False
   • This allows nums[j] to be used in different positions in other permutation branches

Why the duplicate-skipping works: Consider nums = [1, 1, 2] after sorting. When filling a position:

• If we haven't used the first 1 (at index 0), we shouldn't use the second 1 (at index 1)
• This forces us to always use duplicates in order (first 1 before second 1)
• This ordering constraint eliminates duplicate permutations while ensuring all unique ones are generated

The algorithm systematically explores all valid placement choices, using backtracking to undo decisions and try alternatives, ultimately generating all unique permutations in O(n × n!) time complexity.

Example Walkthrough

Let's trace through the algorithm with nums = [1, 1, 2].

Initial Setup:

• Sort the array: nums = [1, 1, 2] (already sorted)
• Initialize: t = [_, _, _], vis = [False, False, False], ans = []

Building the first permutation [1, 1, 2]:

Starting with dfs(0) - filling position 0:

• Try j=0 (nums[0]=1): Not visited, no duplicate issue → Choose it
  • t = [1, _, _], vis = [True, False, False]
  • Call dfs(1) - filling position 1:
    • Try j=0: Skip (already visited)
    • Try j=1 (nums[1]=1): Not visited, but nums[1] == nums[0] and vis[0] = True → Can use it
      • t = [1, 1, _], vis = [True, True, False]
      • Call dfs(2) - filling position 2:
        • Try j=0: Skip (visited)
        • Try j=1: Skip (visited)
        • Try j=2 (nums[2]=2): Not visited → Choose it
          • t = [1, 1, 2], vis = [True, True, True]
          • Call dfs(3): Base case reached → Add [1, 1, 2] to ans
          • Backtrack: vis = [True, True, False]
      • Backtrack: vis = [True, False, False]
    • Try j=2 (nums[2]=2): Not visited → Choose it
      • t = [1, 2, _], vis = [True, False, True]
      • Call dfs(2) - filling position 2:
        • Try j=0: Skip (visited)
        • Try j=1 (nums[1]=1): Not visited, nums[1] == nums[0] but vis[0] = True → Can use it
          • t = [1, 2, 1], vis = [True, True, True]
          • Call dfs(3): Base case → Add [1, 2, 1] to ans
          • Backtrack: vis = [True, False, True]
      • Backtrack: vis = [True, False, False]
  • Backtrack: vis = [False, False, False]

Key moment - Duplicate skipping:

Continue with dfs(0), now trying j=1:

• Try j=1 (nums[1]=1): Not visited, BUT nums[1] == nums[0] and vis[0] = False
  • Skip this! This is the crucial duplicate-avoiding condition
  • If we used the second 1 before the first 1, we'd generate the same permutations

Building the third permutation [2, 1, 1]:

Continue with dfs(0), trying j=2:

• Try j=2 (nums[2]=2): Not visited → Choose it
  • t = [2, _, _], vis = [False, False, True]
  • Call dfs(1) - filling position 1:
    • Try j=0 (nums[0]=1): Not visited → Choose it
      • t = [2, 1, _], vis = [True, False, True]
      • Call dfs(2):
        • Only j=1 is available → Choose it
        • t = [2, 1, 1], vis = [True, True, True]
        • Base case → Add [2, 1, 1] to ans

Final Result: ans = [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

The algorithm successfully generates all 3 unique permutations by:

1. Using backtracking to systematically explore all valid placements
2. Preventing duplicates by enforcing an order when using identical elements (always use the first duplicate before the second)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n! × n)

The algorithm generates all unique permutations using backtracking with pruning for duplicates. In the worst case where all elements are distinct, there are n! permutations. For each permutation:

• The DFS traverses through n positions (depth of recursion tree)
• At each position, it iterates through all n elements to find valid candidates
• When a complete permutation is formed (i == n), it creates a copy of the current permutation t[:] which takes O(n) time

The pruning condition (j and nums[j] == nums[j - 1] and not vis[j - 1]) helps skip duplicate permutations, but doesn't change the worst-case complexity. Therefore, the total time complexity is O(n! × n).

Space Complexity: O(n)

The space complexity consists of:

• t array: O(n) to store the current permutation being built
• vis array: O(n) to track visited elements
• Recursion call stack: O(n) maximum depth
• ans array: O(n! × n) to store all permutations, but this is typically not counted as auxiliary space since it's the required output

Excluding the space for the output, the auxiliary space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Sort the Input Array

One of the most common mistakes is forgetting to sort the input array before starting the backtracking process. Without sorting, duplicate elements are scattered throughout the array, making it impossible to reliably detect and skip duplicate permutations.

Wrong approach:

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    # Missing nums.sort() here!
    result = []
    # ... rest of the code

Why it fails: Without sorting, the condition nums[j] == nums[j-1] won't correctly identify all duplicates since identical elements might not be adjacent.

Solution: Always sort the array first:

nums.sort()  # Critical step - group duplicates together

2. Incorrect Duplicate-Skipping Logic

Another frequent error is using the wrong condition to skip duplicates. A common mistake is:

Wrong condition:

if j > 0 and nums[j] == nums[j-1] and visited[j-1]:  # Wrong!
    continue

Why it fails: This skips using the second duplicate when the first IS used, which is the opposite of what we want. This would generate duplicate permutations.

Correct condition:

if j > 0 and nums[j] == nums[j-1] and not visited[j-1]:  # Correct!
    continue

The logic is: "Skip the current duplicate if the previous duplicate hasn't been used yet." This ensures duplicates are always used in order (first before second).

3. Creating References Instead of Copies

When adding a complete permutation to the result, forgetting to create a copy leads to all permutations in the result pointing to the same array:

Wrong approach:

if index == length:
    result.append(current_permutation)  # Wrong - adds reference!
    return

Why it fails: Since current_permutation is reused and modified throughout the recursion, all entries in result will end up with the same final values.

Solution: Always append a copy:

if index == length:
    result.append(current_permutation[:])  # Correct - creates a copy
    return

4. Not Properly Backtracking the Visited State

Forgetting to reset the visited array after exploring a branch prevents elements from being reused in other permutation branches:

Wrong approach:

visited[j] = True
backtrack(index + 1)
# Missing: visited[j] = False

Why it fails: Once an element is marked as visited, it remains unavailable for all subsequent branches, drastically reducing the number of permutations generated.

Solution: Always reset the state after recursion:

visited[j] = True
backtrack(index + 1)
visited[j] = False  # Critical backtracking step

5. Using Wrong Index in Backtrack Function

Confusing the iteration index j (which element from nums to use) with the position index index (which position in the permutation to fill):

Wrong approach:

def backtrack(index):
    for j in range(length):
        current_permutation[j] = nums[j]  # Wrong - should use index, not j

Solution: Keep the indices straight:

def backtrack(index):
    for j in range(length):
        current_permutation[index] = nums[j]  # Correct - fill position 'index' with nums[j]

These pitfalls can lead to incorrect results, infinite recursion, or missing permutations. Understanding the role of sorting and the duplicate-skipping logic is crucial for this algorithm to work correctly.