https://leetcode.com/problems/permutations-ii/description/
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]
給你一串彼此"可能相同"的數字，把所有排列印出來。
We encounter a similar problem "Print all Permutations" before.
So we wonder if we can apply the same method to this problem, which is
"Imagning we have N slots, pick a number from the remaining numbers, for each slot."
But we can't. Because this time, some of the numbers in the given array might be the same, which will cause a big problem. Let me explain the problem :
For slot x, I am going to pick one from the remaining numbers for it.
But within remaining numbers, there are two or more numbers who have the same value.
So no matter which I choose, it is same for this slot, and same for the remaining numbers.
For example:
For slot 1, I pick first '1' in [1,1,2]. The result is [1, , ], and remaining numbers are [1,2].
For slot 1, I pick second '1' in [1,1,2]. The result is [1, , ], and remaining numbers are [1,2].
Now you can see there is no difference at all no matter which '1' you choose.
So it will be a mistake if you use the previous method(which will treat them as different permutation, but they are not.)
And the solution fot it is :
If you already picked this value for this slot, then you should not choose that value again.
(please note that "value" is not "number". In above example, "value" means 1, "numbers" mease first '1' and second '1'.)
So we implement the solution by add a checking mechanism which check if we already picked this value for this slot.
class Solution {
public:
void buildpermute(vector<int>& nums, int curslot, vector<vector<int>>& res){
if(curslot==nums.size()){
res.push_back(nums);
return;
}
unordered_map<int,int> m;
for(int i=curslot; i<nums.size(); i++){
if(m[nums[i]]++ < 1){ //<--checking mechanism
swap(nums[curslot], nums[i]);
buildpermute(nums, curslot+1 ,res);
swap(nums[curslot], nums[i]);
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
buildpermute(nums,0,res);
return res;
}
};
