题目描述：
给出一个可包含重复数字的序列nums，长度为 $ n $ ，按照任意顺序返回所有不重复的全排列。
数据范围：
$ 1\le n \le 8,-10 \le nums[i] \le 10 $
题解：
首先如果不存在重复数字，就是一个普通的全排列。无须剪枝，直接dfs就好，如题目46. 全排列。
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
33
34
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<vector<int>> ans;
vector<bool> vis;
void dfs(int step, vector<int> &nums, vector<int> cur)
{
if (step == nums.size())
{
ans.emplace_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (vis[i])
continue;
cur.emplace_back(nums[i]);
vis[i] = true;
dfs(step + 1, nums, cur);
vis[i] = false;
cur.pop_back();
}
}
vector<vector<int>> permute(vector<int> &nums)
{
vis.resize(nums.size(), false);
vector<int> cur;
dfs(0, nums, cur);
return ans;
}
};
|
因为存在重复数字，所以需要按照顺序剪枝，例如A,A’,B，A’,A,B为重复序列。首先排序，重复的，填入时，需要从左到右填入第一个未填入的数字。
(num[i] == num[i-1] && !vis[i-1]) continue;
即是相邻的相等的，如果前面那个还没填，这个就不能填。
代码：
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
33
34
35
36
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<vector<int>> ans;
void dfs(vector<int> &nums, int step, vector<int> &cur, vector<bool> &vis)
{
if (step == nums.size())
{
ans.emplace_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (vis[i])
continue;
if (i > 1 && nums[i] == nums[i - 1] && vis[i - 1] == false)
continue;
cur.emplace_back(nums[i]);
vis[i] = true;
dfs(nums, step + 1, cur, vis);
vis[i] = false;
cur.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int> &nums)
{
sort(nums.begin(), nums.end());
vector<bool> vis(nums.size(), false);
vector<int> cur;
dfs(nums, 0, cur, vis);
return ans;
}
};
|