grid47 Exploring patterns and algorithms
Nov 2, 2024
6 min read
Solution to LeetCode 47: Permutations II Problem
Given a collection of numbers that may contain duplicates, generate and return all possible unique permutations of the numbers.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers that may contain duplicates.
Example: [1, 1, 2]
Constraints:
• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10
• Duplicates are allowed in the input array.
Output: Return all unique permutations of the input list.
Example: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Constraints:
• The output must contain only unique permutations.
Goal: The goal is to generate all unique permutations of the given collection of numbers, ensuring that duplicates are not repeated.
Steps:
• 1. Use a backtracking approach to explore all possible permutations of the input list.
• 2. Track the numbers that have already been used in the current permutation to avoid generating duplicate permutations.
• 3. Once a unique permutation is formed, add it to the result list.
Goal: The input array can have a length up to 8. The integers in the array can range from -10 to 10, and there may be duplicate numbers.
Steps:
• The length of the input array is between 1 and 8.
• The integers in the array are between -10 and 10.
• The input may contain duplicate integers.
Assumptions:
• The integers in the input array can be duplicated.
• Input: [1, 1, 2]
• Explanation: For the input [1, 1, 2], the unique permutations are [1, 1, 2], [1, 2, 1], and [2, 1, 1]. The repeated [1, 1, 2] permutation is avoided.
• Input: [1, 2, 3]
• Explanation: For the input [1, 2, 3], all permutations are unique, and the result includes [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].
Approach: The approach to solving this problem is using backtracking to generate permutations while avoiding duplicates.
Observations:
• The number of permutations grows factorially with the size of the input array.
• To avoid duplicate permutations, we need to track previously visited elements during the backtracking process.
• A backtracking approach works well for this problem, but we must ensure that we don't revisit numbers that have already been used in the current permutation.
Steps:
• 1. Start by sorting the input array to group duplicates together.
• 2. Use backtracking to generate all possible permutations, but skip numbers that have already been used in the current iteration to avoid duplicates.
• 3. Add each unique permutation to the result list.
Empty Inputs:
• The input will never be empty as per the given constraints (minimum array length is 1).
Large Inputs:
• The maximum input size is 8, so the factorial growth of the number of permutations will not exceed manageable limits.
Special Values:
• The input array can contain duplicates, so we need to be mindful of handling them in the backtracking process.
Constraints:
• Ensure to handle duplicate numbers properly to avoid generating the same permutation multiple times.
This line declares a recursive backtracking function `f` that takes three arguments: `nums` (the input array), `ans` (a 2D vector to store the permutations), and `ind` (the current index).
2 : Base Case
if(ind==nums.size()){
This line checks if the current index `ind` has reached the end of the array. If so, it means a complete permutation has been formed.
3 : Add Permutation to Result
ans.push_back(nums);
If the base case is true, the current permutation `nums` is added to the `ans` vector.
4 : Return from Base Case
return;
The function returns after adding the permutation to the result.
5 : Map Initialization
unordered_map<int,int>mp;
An unordered map `mp` is initialized to keep track of the frequency of each number in the current permutation. This is used to avoid duplicate permutations.
6 : Loop Iteration
for(int i=ind;i<nums.size();i++){
This loop iterates through the elements of the array starting from the current index `ind`.
7 : Skip Duplicate Numbers
if(mp.find(nums[i])!=mp.end()){
This condition checks if the current number `nums[i]` has already been used in the current permutation. If so, it skips to the next iteration.
8 : Skip Duplicate Numbers
continue;
The `continue` statement skips to the next iteration of the loop.
9 : Mark Number as Used
}else{
If the current number is not a duplicate, it is marked as used in the `mp` map.
10 : Mark Number as Used
mp[nums[i]]++;
The frequency of the current number `nums[i]` is incremented in the `mp` map.
11 : Swap Elements
swap(nums[i],nums[ind]);
The current number `nums[i]` is swapped with the number at the current index `ind` to explore a new permutation.
12 : Recursive Call
f(nums,ans,ind+1);
The `f` function is recursively called with the updated `ind` to explore the next position in the permutation.
13 : Backtrack
swap(nums[i],nums[ind]);
After the recursive call, the swap operation is reversed to backtrack and explore other possibilities.
This line declares the main function `permuteUnique` that takes a vector of integers `nums` as input and returns a vector of vectors containing all unique permutations.
15 : Result Vector Initialization
vector<vector<int>>ans;
A 2D vector `ans` is initialized to store the unique permutations.
16 : Backtracking Function Call
f(nums,ans,0);
The `f` function is called with the `nums` array, `ans` vector, and starting index `0` to initiate the backtracking process.
17 : Return Result
return ans;
The `ans` vector containing all unique permutations is returned.
Best Case: O(n!)
Average Case: O(n!)
Worst Case: O(n!)
Description: The time complexity is O(n!) due to the need to generate all possible permutations of n elements, where n is the length of the input array.
Best Case: O(n!)
Worst Case: O(n!)
Description: The space complexity is O(n!) because we need to store all unique permutations, and the recursive stack may also reach this depth.
