题目
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
分析
这题与上一题的不同之处为可能含有相同的元素。那么对于结果的每一位，只要跳过之前出现过的数字即可。需要注意的是，这一位的跳过不能影响下一位的使用。对于第46题稍作修改即可。
实现
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(), false);
vector<int> path;
vector<vector<int>> ans;
solve(nums, used, path, ans);
return ans;
}
private:
void solve(vector<int> &nums, vector<bool> &used,
vector<int> &path, vector<vector<int>> &ans){
if(path.size()==nums.size()){
ans.push_back(path);
return;
}
for(int i=0; i<nums.size(); i++){
if(used[i]) continue;
if(i!=0 && nums[i]==nums[i-1] && !used[i-1]) continue;
used[i] = true;
path.push_back(nums[i]);
solve(nums, used, path, ans);
path.pop_back();
used[i] = false;
}
}
};
思考
偷懒的做法也可以直接使用std::permutation()==
但是这对于提高毫无作用，面试的时候考官也肯定会让你重新实现的。
另外看题解的时候发现了c++中也有for_each()感觉很神奇，赶紧恶补了下。
然而有些还是看不懂...c++果然可怕==
