题目
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
分析
这道题目给定的数组中存在重复数字，我们可以先将数字排序，然后在枚举$pos$的时候只枚举不同的元素，如果当前元素已经在当前位置被枚举过了，则跳过，保证每个位置每个元素只会被枚举一次。
需要特别注意的是跳过条件，如果我们只是单纯的采用如下条件判断：
1
| if (i > 0 && nums[i] == nums[i - 1])
|
这会导致枚举下一个位置的时候，也无法枚举相同的元素，比如1，1，2。当我们在第一个位置枚举了1，第二个位置就不能枚举1了，会被跳过。所以我们需要添加一个条件，只有当上一个位置的重复元素没有被访问的时候，我们才跳过，否则我们不应该跳过。
1
| if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
cur = vector<int>(nums.size(), 0);
vis = vector<bool>(nums.size(), false);
sort(nums.begin(), nums.end());
backtrack(nums, 0);
return ans;
}
void backtrack(vector<int> &nums, int pos)
{
if (pos == nums.size())
{
ans.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (vis[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])
continue;
vis[i] = true;
cur[pos] = nums[i];
backtrack(nums, pos + 1);
vis[i] = false;
}
}
private:
vector<vector<int>> ans;
vector<int> cur;
vector<bool> vis;
};
|