Introduction
LeetCode 47: Permutations II is an extension of the Permutations problem. The challenge here is to generate all distinct permutations of a collection of numbers, which may contain duplicates.
The main difference from LeetCode 46: Permutations is that we need to avoid generating duplicate permutations. This requires a slightly modified approach where we handle duplicates during the recursion step.
This problem can be solved efficiently using backtracking combined with sorting and a mechanism to skip over repeated elements.
Problem Statement
Given a collection of numbers that may contain duplicates, return all possible unique permutations.
Example 1:
go
Input: nums = [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Example 2:
go
Input: nums = [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Approach: Backtracking with Handling Duplicates
The approach involves backtracking but with an additional step of sorting the input array and using a used array to track which elements have been considered for the current position. By sorting the input array, we ensure that duplicates are adjacent, making it easy to skip over them during the recursion step.
Steps:
- Sort the Array: Sorting ensures that duplicates are adjacent, which allows us to easily skip duplicates.
- Backtracking: At each index, try to use each element in the current position, but ensure we don't use the same element twice in a given recursion level.
- Used Array: A
used array helps track which elements have been used in the current recursive call.
- Skip Duplicates: If an element is the same as the previous element and the previous element has not been used in the current recursion, skip it to avoid generating duplicate permutations.
Go Implementation
go
func permuteUnique(nums []int) [][]int {
var res [][]int
sort.Ints(nums) // Sort the input to handle duplicates
backtrack(nums, []int{}, &res, make([]bool, len(nums)))
return res
}
func backtrack(nums []int, current []int, res *[][]int, used []bool) {
// If the current permutation is complete, add it to the result
if len(current) == len(nums) {
temp := make([]int, len(nums))
copy(temp, current)
*res = append(*res, temp)
return
}
for i := 0; i < len(nums); i++ {
// Skip used elements or duplicate elements that haven't been used yet
if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue
}
// Mark the current element as used and recurse
used[i] = true
backtrack(nums, append(current, nums[i]), res, used)
used[i] = false // Backtrack and mark the element as unused
}
}
Example Walkthrough
Example 1:
go
Input: nums = [1,1,2]
- Initial Call:
backtrack([1, 1, 2], [], res, used)
- Sort
nums: [1, 1, 2]
- Start at index
0, attempt to place 1 at the first position.
- Recursively generate permutations:
backtrack([1, 1, 2], [1], res, used)
- Next, try placing
1 again at the second position.
- Recursively generate permutations:
backtrack([1, 1, 2], [1, 1], res, used)
- Finally, place
2 in the last position.
- Base case: Record permutation
[1, 1, 2].
- Backtrack, and try other combinations while skipping duplicates.
- Final Output:
go
[
[1, 1, 2],
[1, 2, 1],
[2, 1, 1]
]
Example 2:
go
Input: nums = [1, 2, 3]
- Initial Call:
backtrack([1, 2, 3], [], res, used)
- Sort
nums: [1, 2, 3]
- Start at index
0, place 1 first and recursively generate permutations for [2, 3].
- Continue with
2 and 3 at the next recursive levels, ensuring no duplicates are generated.
- All permutations are recorded.
- Final Output:
go
[
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]
Time and Space Complexity
MetricComplexityTime ComplexityO(n!)Space ComplexityO(n)
- Time Complexity: The number of unique permutations for
n distinct elements is n!, so the time complexity remains O(n!). The sorting step is O(n log n), but the backtracking dominates the complexity.
- Space Complexity: The space complexity is O(n) due to the recursion stack and the storage of the result, where
n is the length of the input array.
Edge Cases
- Single Element: A single-element array has only one permutation.
- Input:
[1]
- Output:
[[1]]
- All Elements Identical: If the array contains the same element repeated, there will be only one unique permutation.
- Input:
[2, 2, 2]
- Output:
[[2, 2, 2]]
- Empty Array: An empty array has only one permutation, which is the empty array itself.
- Input:
[]
- Output:
[[]]
Key Takeaways
- Backtracking with duplicate handling is crucial for problems like this, where we need to ensure unique permutations while respecting constraints.
- Sorting the input array ensures that duplicates are adjacent, making it easy to skip over them during the recursion step.
- The approach can be generalized to problems requiring the generation of unique combinations or permutations with repetition.