题目描述
给定一个可包含重复数字的序列,返回所有不重复的全排列。
样例
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
dfs
class Solution { // 代码参考yxc
public:
vector<vector<int>> ans;
vector<int> path;
vector<bool> st;
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
st = vector<bool>(nums.size(),false);
path = vector<int>(nums.size());
dfs(nums, 0, 0);
return ans;
}
void dfs(vector<int>& nums, int u, int start){
if(u == nums.size()) // u 表示当前位置 start 表示从哪里开始枚举数字
{
ans.push_back(path);
return;
}
for(int i=start;i<nums.size();i++)
{
if(!st[i])
{
st[i] = true;
path[i] = nums[u];
if(u+1<nums.size() && nums[u+1]!=nums[u]) // 如果下一个数字和当前数字不重复,则从0开始
dfs(nums, u+1, 0);
else dfs(nums,u+1,i+1); // 下一个数字和当前数字重复,人为排序,从下一个开始
st[i] = false;
}
}
}
};