#47

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Permutations II

Generate all unique permutations of an array containing duplicates using backtracking and pruning to avoid repeated sequences efficiently.

array backtracking sorting

Problem Statement

Given an array of integers nums, which may contain duplicates, return all unique permutations in any order. Each permutation must be represented as a separate array, and the solution should avoid duplicate sequences that result from repeated numbers. The goal is to generate all possible orderings without repetition efficiently.

For example, given nums = [1,1,2], the output should be [[1,1,2],[1,2,1],[2,1,1]]. The constraints are 1 <= nums.length <= 8 and -10 <= nums[i] <= 10. Careful handling of duplicates and proper pruning during backtracking are essential to meet time and space requirements for larger inputs.

Examples

Example 1

Input: nums = [1,1,2]

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

Example details omitted.

Example 2

Input: nums = [1,2,3]

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

Example details omitted.

Constraints

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

Solution Approach

Sort the Array to Handle Duplicates

Begin by sorting the input array to ensure duplicate numbers are adjacent. Sorting allows the backtracking process to detect consecutive identical elements and skip them when they have already been used in the current recursive path. This initial step is crucial because it directly supports the pruning strategy, reducing redundant exploration and ensuring that the generated permutations remain unique.

Backtracking with Used Tracking

Implement a recursive backtracking function that constructs permutations by exploring each number not yet used. Maintain a boolean array indicating which elements are included in the current path. At each recursion level, skip any element that is equal to the previous element if the previous one has not been used, preventing duplicate permutations. This strategy ensures each branch represents a unique sequence while exploring all valid combinations.

Prune Duplicate Paths During Recursion

During recursion, check for consecutive duplicates and only proceed with the first unused instance of a number. If the current number is the same as the previous one and the previous was not used in this branch, skip it. This pruning mechanism significantly reduces unnecessary recursive calls, prevents generating repeated permutations, and keeps the algorithm efficient, especially for arrays with multiple duplicate values.

Complexity Analysis

Metric	Value
Time	\mathcal{O}\big(\sum_{k = 1}^{N}{P(N, k)}\big)
Space	\mathcal{O}(N)

The time complexity of this approach is O(∑_{k=1}^{N} P(N, k)) because it generates all unique permutations with pruning to skip duplicates, and the space complexity is O(N) due to recursion and tracking used elements.

What Interviewers Usually Probe

Do you understand how sorting helps prune duplicate paths in backtracking for this problem?
Can you implement the used-element tracking to avoid repeated sequences efficiently?
Will you explain how skipping a duplicate number affects the recursion tree and total permutations?

Common Pitfalls or Variants

Common pitfalls

Failing to sort the input array before backtracking, causing duplicate permutations to appear in the output.
Not properly skipping a duplicate element when the previous identical element hasn't been used, leading to repeated sequences.
Modifying the current path without restoring state after recursion, resulting in incorrect permutations being carried forward.

Follow-up variants

Generate all unique subsets of an array with possible duplicates, requiring backtracking with pruning similar to this problem.
Permutations without duplicates: Given an array with distinct numbers, generate all permutations, a simpler variant without duplicate checks.
Count the number of unique permutations for large N with duplicates, focusing on combinatorial calculation rather than explicit generation.

FAQ

How does sorting assist with generating unique permutations in Permutations II?

Sorting ensures duplicate numbers are adjacent, which allows the backtracking algorithm to skip repeated elements efficiently, preventing duplicate permutations from being generated.

What is the role of the used-element tracking array in this problem?

The boolean array tracks which elements are included in the current permutation path. Skipping elements that are already used in the current branch avoids repeating numbers and maintains correct sequences.

How does pruning prevent redundant recursive calls in backtracking?

Pruning skips elements that are identical to the previous unused element, reducing the number of unnecessary recursive calls and ensuring each branch explores a unique permutation path.

Can Permutations II handle negative numbers and zeros?

Yes, the algorithm correctly handles negative numbers, zeros, and duplicates as long as the array is sorted first and backtracking with pruning is applied to skip duplicates.

Why is backtracking with pruning the preferred pattern for this problem?

Backtracking systematically explores all possible sequences, and pruning duplicates prevents repeated permutations, making it both correct and efficient for arrays with repeated numbers.

terminal

Solution

Solution 1: Sorting + Backtracking

We can first sort the array so that duplicate numbers are placed together, making it easier to remove duplicates.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i == n:
                ans.append(t[:])
                return
            for j in range(n):
                if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):
                    continue
                t[i] = nums[j]
                vis[j] = True
                dfs(i + 1)
                vis[j] = False

        n = len(nums)
        nums.sort()
        ans = []
        t = [0] * n
        vis = [False] * n
        dfs(0)
        return ans

Continue Practicing

#49 group anagrams #37 sudoku solver #75 sort colors