leetcode_47全排列II
1. 题意
给一个含有重复数字的数组，求不重复的排列。
2. 题解
将数组进行排序，当回溯发生的时候，找到下个不重复的元素即可。
class Solution {
public:
void genPerm(std::vector<std::vector<int>> &ans, std::vector<int> &tmp,
std::vector<int> &a, std::vector<int> &vis)
{
int sz = a.size();
if (tmp.size() == sz) {
ans.emplace_back( tmp );
return ;
}
for (int i = 0;i < sz; i++) {
if (!vis[i] ) {
vis[i] = 1;
tmp.push_back(a[i]);
genPerm(ans, tmp, a, vis);
tmp.pop_back();
vis[i] = 0;
while (i + 1 < sz && a[i + 1] == a[i])
i++;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> vis(nums.size(), 0);
vector<int> tmp;
genPerm(ans, tmp, nums, vis);
return ans;
}
};