Problem Statement
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
- Note: A permutation is a rearrangement of the elements of an array.
Example Inputs
Example 1:
Approach
To generate all unique permutations of the given array nums, especially when it contains duplicates, we can use a recursive backtracking approach combined with sorting and pruning to avoid duplicate permutations.
Steps
-
Sort the Array:
- Begin by sorting the
nums array. Sorting helps in easily identifying duplicates and skipping them during permutation generation.
-
Initialize:
- Create an empty array
ans to store all valid unique permutations.
- Create an empty array
current to build the current permutation.
- Use a boolean array
used of the same length as nums to keep track of elements that have been included in the current permutation to avoid using the same element multiple times.
-
Recursive Backtracking Function (backtrack):
-
Parameters:
current: The current permutation being built.used: Array indicating whether an element has been used in the current permutation.
-
Base Case:
- If the length of
current equals the length of nums, it means a complete permutation has been formed. Add a copy of current to ans.
-
Recursive Case:
- Iterate through each element in
nums.
- For each element at index
i:
- Skip Used Elements: If
used[i] is true, skip to avoid reusing the same element.
- Skip Duplicates: If
i > 0, nums[i] is the same as nums[i - 1], and used[i - 1] is false, skip to avoid generating duplicate permutations.
- Include the Element:
- Mark
used[i] as true.
- Add
nums[i] to current.
- Recursively call
backtrack to continue building the permutation.
- Remove the last element from
current (backtrack) and mark used[i] as false to explore other possibilities.
-
Start Backtracking:
- Call the
backtrack function with an empty current array and the initialized used array.
-
Return the Result:
- After exploring all possibilities, return the
ans array containing all unique permutations.
Time & Space Complexity
-
Time Complexity: O(n!),
- In the worst case, where all elements are unique, the number of permutations is
n!.
- When there are duplicates, the number of unique permutations decreases, but the upper bound remains
O(n!).
-
Space Complexity: O(n),
- The space required for the recursion stack and the
current permutation array is O(n).
Code Snippet
Dry Run
Let's perform a dry run with nums = [1, 1, 2].
-
Initial Setup:
nums after sorting: [1, 1, 2]ans = []current = []used = [false, false, false]
-
First Call: backtrack()
current = []used = [false, false, false]
-
First Level:
- i = 0: Number = 1
- Include 1:
current = [1]used = [true, false, false]- Recurse:
backtrack()
-
Second Level:
- i = 0: Already used, skip.
- i = 1: Number = 1
- Include 1:
current = [1, 1]used = [true, true, false]- Recurse:
backtrack()
-
Third Level:
- i = 0: Already used, skip.
- i = 1: Already used, skip.
- i = 2: Number = 2
- Include 2:
current = [1, 1, 2]used = [true, true, true]- Recurse:
backtrack()
-
Base Case Reached:
- Add
[1, 1, 2] to ans: ans = [[1, 1, 2]]
- Backtrack: Remove
2, current = [1, 1], used = [true, true, false]
-
Back to Third Level:
- All elements processed.
- Backtrack: Remove
1, current = [1], used = [true, false, false]
-
Back to Second Level:
- i = 2: Number = 2
- Include 2:
current = [1, 2]used = [true, false, true]- Recurse:
backtrack()
-
Third Level:
- i = 0: Already used, skip.
- i = 1: Number = 1
- Include 1:
current = [1, 2, 1]used = [true, true, true]- Recurse:
backtrack()
-
Base Case Reached:
- Add
[1, 2, 1] to ans: ans = [[1, 1, 2], [1, 2, 1]]
- Backtrack: Remove
1, current = [1, 2], used = [true, false, true]
-
Back to Third Level:
- i = 2: Already used, skip.
- Backtrack: Remove
2, current = [1], used = [true, false, false]
-
Back to Second Level:
- All elements processed.
- Backtrack: Remove
1, current = [], used = [false, false, false]
-
First Level (continued):
- i = 1: Number = 1 (Duplicate of previous and
used[0] is false, so skip to avoid duplicate)
- i = 2: Number = 2
- Include 2:
current = [2]used = [false, false, true]- Recurse:
backtrack()
-
Second Level:
- i = 0: Number = 1
- Include 1:
current = [2, 1]used = [true, false, true]- Recurse:
backtrack()
-
Third Level:
- i = 0: Already used, skip.
- i = 1: Number = 1
- Include 1:
current = [2, 1, 1]used = [true, true, true]- Recurse:
backtrack()
-
Base Case Reached:
- Add
[2, 1, 1] to ans: ans = [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
- Backtrack: Remove
1, current = [2, 1], used = [true, false, true]
-
Back to Third Level:
- i = 2: Already used, skip.
- Backtrack: Remove
1, current = [2], used = [false, false, true]
-
Back to Second Level:
- i = 1: Number = 1
- Include 1:
current = [2, 1] (Already included in previous step)- Since
nums[1] is the same as nums[0] and used[0] is false, skip to avoid duplicate.
- Backtrack: Remove
2, current = [], used = [false, false, false]
-
Final Result: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Complexity Analysis
-
Time Complexity: O(n!),
- In the worst case, where all elements are unique, the number of unique permutations is
n!.
- When duplicates are present, the number of unique permutations is reduced but still upper bounded by
O(n!).
-
Space Complexity: O(n),
- The space required for the recursion stack and the
current permutation array is O(n).
Optimizations:
- Sorting and Skipping Duplicates:
- Sorting the array allows us to easily skip over duplicate elements, ensuring that we do not generate duplicate permutations.
- Using a Boolean Array for Tracking:
- Using a
used array helps in efficiently tracking which elements have been included in the current permutation, avoiding the need for more complex data structures like sets.
Conclusion
The Permutations II problem is a classic example of using recursive backtracking to explore all unique arrangements of a set of elements, especially when duplicates are present. By sorting the input array and implementing strategic pruning to skip duplicates, we can efficiently generate all valid unique permutations without redundancy.
Understanding this approach not only aids in solving similar combinatorial problems but also reinforces fundamental concepts in recursion, backtracking, and algorithm optimization. Implementing the solution in a functional style without using classes makes the code more concise and accessible, especially for beginners. By carefully managing the state and making strategic choices at each step, complex permutation problems become manageable and solvable with clarity and confidence.