给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
题解
一定要先看上一题 力扣 46. 全排列 [设置/不设置 标志数组]
因为可以重复,所以先来一个排序,方便后面处理重复,当面对下标i时,如果nums[i]与nums[i-1]相等,应该加以判断是否选择i
接下来按上一题的代码画图捋一下[1,1,2],取第二个1为1',[1,1',2],
面对1'时,因为1等于1':
- 如果之前选择过
1,说明之前肯定以[1,1']为开头去搜索其余的元素了,此时如果选择1'则会以[1',1]为开头去重复计算 - 如果之前没有选择过
1,现在选择1',不会造成重复.
示意图如下:
所以前面说的加以判断是判定之前的1是否被使用过,如果没有用过才可以选择当前的1',如果用过就没有选择当前1',i>0&&nums[i]==nums[i-1]&&!flag[i-1]),综合当前元素是否使用过flag[i]得到for循环中的如下判断:
//当前用过,就跳过
//如果和上一个相等且上一个没有选过，就跳过
if(flag[i]||(i>0&&nums[i]==nums[i-1]&&!flag[i-1]))
continue;查看代码
class Solution {
public:
vector<vector<int>> res;
bool flag[8]={false};
void dfs(vector<int>& cur,vector<int> nums,int len){
if(cur.size()==len)
{
res.emplace_back(cur);
return;
}
for(int i=0;i<len;i++){
//当前用过,就跳过
//如果和上一个相等且上一个没有选过，就跳过
if(flag[i]||(i>0&&nums[i]==nums[i-1]&&!flag[i-1]))
continue;
flag[i]=!flag[i];
cur.emplace_back(nums[i]);
dfs(cur,nums,len);
flag[i]=!flag[i];
cur.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<int> cur;
dfs(cur,nums,nums.size());
return res;
}
};