LeetCode 47 - Permutations II
The problem asks us to generate every possible permutation of the given array nums, while ensuring that duplicate permutations are not included in the final result. A permutation is an arrangement of all elements in a particular order.
Difficulty: 🟡 Medium
Topics: Array, Backtracking, Sorting
Solution
Problem Understanding
The problem asks us to generate every possible permutation of the given array nums, while ensuring that duplicate permutations are not included in the final result.
A permutation is an arrangement of all elements in a particular order. For example, the permutations of [1,2,3] are all six possible orderings of those three numbers.
The complication in this problem is that the input array may contain duplicate values. If we generate permutations naively, duplicate numbers can lead to repeated permutations. For example, with nums = [1,1,2], swapping the two 1s does not create a new unique arrangement, even though a brute-force permutation generator would treat them as different positions.
The input is an integer array nums, and the output should be a list containing every unique permutation. The order of the returned permutations does not matter.
The constraints are relatively small:
1 <= nums.length <= 8-10 <= nums[i] <= 10
The maximum array size of 8 is important because permutations grow factorially. Even with no duplicates, there can be 8! = 40320 permutations, which is large but still manageable with an efficient backtracking solution.
Several edge cases are important:
- Arrays containing all duplicate values, such as
[1,1,1] - Arrays containing no duplicates, such as
[1,2,3] - Arrays containing negative numbers
- Arrays where duplicates appear multiple times, such as
[1,1,2,2]
A naive implementation can easily generate duplicate permutations repeatedly, which wastes time and memory. The key challenge is avoiding duplicates efficiently during generation, rather than filtering them afterward.
Approaches
Brute Force Approach
A straightforward approach is to generate every possible permutation of the array, even if duplicates are produced. After generating all permutations, we can insert each permutation into a set to remove duplicates.
This works because a set only keeps unique entries. However, this method is inefficient because it still generates many redundant permutations when duplicates exist.
For example, if the input is [1,1,2], the brute-force algorithm treats the two 1s as distinct positions and generates:
[1,1,2][1,2,1][1,1,2][1,2,1][2,1,1][2,1,1]
Half of the work is redundant.
The factorial growth of permutations already makes the problem expensive. Generating duplicates unnecessarily increases both runtime and memory usage.
Optimal Approach
The better solution uses backtracking with sorting and duplicate skipping.
The key insight is that duplicate values only cause duplicate permutations when they are used in the same decision position multiple times.
By sorting the array first, duplicate values become adjacent. During backtracking, we can skip choosing a duplicate number if the previous identical number has not been used in the current recursive branch.
This prevents generating equivalent branches of the recursion tree.
For example, after sorting [1,1,2], when considering the second 1, we only allow it if the first 1 has already been used in the current permutation path. This guarantees that identical numbers are chosen in a consistent order, eliminating duplicate permutations entirely.
This approach avoids redundant work instead of cleaning duplicates afterward.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n! × n) | O(n! × n) | Generates all permutations including duplicates, then removes duplicates using a set |
| Optimal | O(n! × n) | O(n) excluding output | Uses backtracking with sorting and duplicate pruning to avoid redundant permutations |
Algorithm Walkthrough
- Sort the input array.
Sorting places duplicate values next to each other. This is essential because it allows us to detect duplicates during backtracking.
For example:
[1,1,2]
The duplicate 1s are adjacent, making duplicate checks easy.
2. Create a used array.
The used array keeps track of which indices have already been included in the current permutation.
Example:
used = [False, False, False]
If used[i] is True, then nums[i] is already part of the current permutation path.
3. Start backtracking with an empty current permutation.
We recursively build permutations one element at a time.
At each recursive level, we try every unused number. 4. Skip already used elements.
If used[i] is True, we skip that element because each element can only appear once in a single permutation.
5. Skip duplicate choices intelligently.
This is the most important step.
When processing nums[i], if:
nums[i] == nums[i - 1]
and the previous identical element has not been used:
not used[i - 1]
then we skip the current element.
This prevents generating duplicate recursive branches.
The logic means:
"Only use the second duplicate if the first duplicate has already been chosen in this branch." 6. Choose an element.
Add the current number to the permutation path and mark it as used. 7. Recurse deeper.
Continue building the permutation until its length equals len(nums).
8. Record a complete permutation.
Once the permutation contains all elements, append a copy to the result list. 9. Backtrack.
Remove the last element from the path and mark it as unused so other branches can explore different possibilities.
Why it works
The algorithm guarantees uniqueness because duplicates are only allowed in a fixed ordering during recursion. Sorting ensures identical numbers are adjacent, and the duplicate-skipping rule prevents identical recursive branches from being explored multiple times. Every valid unique permutation is generated exactly once.
Python Solution
from typing import List
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
current_permutation = []
used = [False] * len(nums)
def backtrack():
if len(current_permutation) == len(nums):
result.append(current_permutation[:])
return
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
current_permutation.append(nums[i])
backtrack()
current_permutation.pop()
used[i] = False
backtrack()
return result
The implementation begins by sorting the array so duplicate values are adjacent. This enables the duplicate-skipping condition later in the algorithm.
The result list stores all completed permutations. The current_permutation list tracks the permutation currently being built. The used array records which indices have already been selected.
The backtrack() function performs the recursive search.
The base case occurs when the current permutation length equals the input length. At that point, a copy of the permutation is appended to the result list.
Inside the loop, the algorithm first skips already used elements. Then it applies the duplicate-skipping rule:
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
This condition ensures that duplicate values are selected in a consistent order, preventing duplicate permutations.
After choosing a number, the algorithm marks it as used, appends it to the current path, and recursively explores deeper permutations.
After recursion finishes, the algorithm backtracks by removing the number and resetting its used state.
Go Solution
func permuteUnique(nums []int) [][]int {
result := [][]int{}
sort.Ints(nums)
used := make([]bool, len(nums))
current := []int{}
var backtrack func()
backtrack = func() {
if len(current) == len(nums) {
permutation := make([]int, len(current))
copy(permutation, current)
result = append(result, permutation)
return
}
for i := 0; i < len(nums); i++ {
if used[i] {
continue
}
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue
}
used[i] = true
current = append(current, nums[i])
backtrack()
current = current[:len(current)-1]
used[i] = false
}
}
backtrack()
return result
}
The Go implementation follows the same algorithmic structure as the Python version.
One important difference is that slices in Go are references to underlying arrays. Because of this, when storing a completed permutation, we must create a copy using copy() before appending it to result. Otherwise, future modifications during backtracking would affect previously stored permutations.
The used slice behaves similarly to the Python boolean list.
Go does not require special handling for integer overflow here because the problem constraints are very small.
Worked Examples
Example 1
Input:
nums = [1,1,2]
After sorting:
[1,1,2]
Initial state:
| Step | Current Permutation | Used | Action |
|---|---|---|---|
| 1 | [] | [F,F,F] | Start recursion |
Choose first 1:
| Step | Current Permutation | Used | Action |
|---|---|---|---|
| 2 | [1] | [T,F,F] | Choose index 0 |
Choose second 1:
| Step | Current Permutation | Used | Action |
|---|---|---|---|
| 3 | [1,1] | [T,T,F] | Choose index 1 |
Choose 2:
| Step | Current Permutation | Used | Action |
|---|---|---|---|
| 4 | [1,1,2] | [T,T,T] | Complete permutation |
Backtrack and try another choice:
| Step | Current Permutation | Used | Action |
|---|---|---|---|
| 5 | [1,2] | [T,F,T] | Choose index 2 |
Then choose second 1:
| Step | Current Permutation | Used | Action |
|---|---|---|---|
| 6 | [1,2,1] | [T,T,T] | Complete permutation |
Backtrack to root.
Now consider second 1 at root:
nums[1] == nums[0]
and used[0] == False
So we skip it to avoid duplicates.
Choose 2:
| Step | Current Permutation | Used | Action |
|---|---|---|---|
| 7 | [2] | [F,F,T] | Choose index 2 |
Then build:
[2,1,1]
Final result:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Example 2
Input:
nums = [1,2,3]
Since there are no duplicates, the duplicate-skipping condition never triggers.
The recursion explores every possible ordering:
| Current Permutation | Next Choices |
|---|---|
| [] | 1,2,3 |
| [1] | 2,3 |
| [1,2] | 3 |
| [1,3] | 2 |
| [2] | 1,3 |
| [2,1] | 3 |
| [2,3] | 1 |
| [3] | 1,2 |
Final output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n! × n) | There can be up to n! unique permutations, and copying each permutation costs O(n) |
| Space | O(n) excluding output | Recursion stack, current permutation, and used array each require O(n) space |
The factorial complexity comes from the number of possible permutations. In the worst case where all numbers are distinct, there are n! permutations.
Each completed permutation requires copying n elements into the result list, leading to the extra multiplicative factor of n.
The auxiliary space is linear because the recursion depth never exceeds n, and both the used array and current permutation store at most n elements.
Test Cases
from typing import List
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
current = []
used = [False] * len(nums)
def backtrack():
if len(current) == len(nums):
result.append(current[:])
return
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
current.append(nums[i])
backtrack()
current.pop()
used[i] = False
backtrack()
return result
solution = Solution()
# Example with duplicates
assert sorted(solution.permuteUnique([1,1,2])) == sorted([
[1,1,2],
[1,2,1],
[2,1,1]
])
# Example with all distinct values
assert sorted(solution.permuteUnique([1,2,3])) == sorted([
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
])
# Single element array
assert solution.permuteUnique([5]) == [[5]]
# All elements identical
assert solution.permuteUnique([2,2,2]) == [[2,2,2]]
# Two duplicates and one unique
assert sorted(solution.permuteUnique([1,1,2])) == sorted([
[1,1,2],
[1,2,1],
[2,1,1]
])
# Negative numbers
assert sorted(solution.permuteUnique([-1,-1,2])) == sorted([
[-1,-1,2],
[-1,2,-1],
[2,-1,-1]
])
# Larger duplicate set
assert sorted(solution.permuteUnique([1,1,2,2])) == sorted([
[1,1,2,2],
[1,2,1,2],
[1,2,2,1],
[2,1,1,2],
[2,1,2,1],
[2,2,1,1]
])
# Mixed duplicates
assert sorted(solution.permuteUnique([1,2,2,3])) == sorted([
[1,2,2,3],
[1,2,3,2],
[1,3,2,2],
[2,1,2,3],
[2,1,3,2],
[2,2,1,3],
[2,2,3,1],
[2,3,1,2],
[2,3,2,1],
[3,1,2,2],
[3,2,1,2],
[3,2,2,1]
])
| Test | Why |
|---|---|
[1,1,2] |
Validates duplicate handling |
[1,2,3] |
Verifies standard permutation generation |
[5] |
Tests smallest valid input |
[2,2,2] |
Ensures duplicates collapse into one permutation |
[-1,-1,2] |
Verifies negative numbers work correctly |
[1,1,2,2] |
Tests multiple duplicate groups |
[1,2,2,3] |
Validates mixed duplicate and unique values |
Edge Cases
All Elements Are Identical
An input such as:
[1,1,1]
can easily cause duplicate permutations in naive implementations because swapping identical elements produces the same arrangement repeatedly.
The duplicate-skipping condition prevents this issue. Only the first unused duplicate at each recursion level is allowed, so the algorithm generates exactly one permutation:
[[1,1,1]]
No Duplicates Exist
An input such as:
[1,2,3]
contains only distinct values. In this situation, the duplicate-skipping condition never activates because adjacent values are never equal.
The algorithm naturally reduces to standard permutation backtracking and generates all n! permutations correctly.
Multiple Duplicate Groups
Inputs like:
[1,1,2,2]
are especially error-prone because duplicate handling must work independently across multiple value groups.
Incorrect implementations may still generate repeated permutations or accidentally skip valid ones.
The sorted-array strategy combined with the condition:
nums[i] == nums[i - 1] and not used[i - 1]
ensures that duplicates are handled consistently for every value group, guaranteeing that every unique permutation appears exactly once.