题目描述:
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
思路
排列的问题就用回溯。
由于nums数组中可能有相同的数字,所以在全排列时会出现重复的排列。这就需要剪枝。思路如下:
首先将nums数组进行排序,让相同的数字紧邻;
然后在递归填入数字的过程中每次都需要遍历vis
数组来查找未被使用过的数字,这样我们只寻找未被使用的数字中的第一个,例如nums = [1, 1, 2]
,当第一个1开头的所有排列情况都被找到后,开始寻找第二个1开头的排列,这时的vis = [0, 0, 0]
,表示三个数字都未被使用,但是对于第2个1来说,前一个数字和它相同却未被使用,说明这种情况之前出现过,可以直接continue
跳过。剪枝的代码为:
if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
//剪枝,避免填入这个位置曾经填入过的数字
continue;
}
题解:
class Solution {
vector<bool> vis;
public:
void backtrace(int idx, vector<int>& tmp, vector<vector<int>>& ans, vector<int>& nums) {
if (idx == nums.size()) { //idx与size相等,说明已经填完了所有的数字,此时的tmp存储的是一个
//合法答案,将其加入ans数组,并返回。
ans.emplace_back(tmp);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
//剪枝,避免填入这个位置曾经填入过的数字
continue;
}
if (!vis[i]) {
tmp.emplace_back(nums[i]);
vis[i] = 1;
backtrace(idx + 1, tmp, ans, nums);
vis[i] = 0;
tmp.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vis.resize(nums.size());
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> tmp;
backtrace(0, tmp, ans, nums);
return ans;
}
};