LeetCode 47 全排列 II - 回溯解法
https://leetcode.cn/problems/permutations-ii/description/
思路
和[全排列](LeetCode 46 全排列 - 回溯解法.md) 类似， 只不过这里需要去重
这里的重复是 for 循环的重复，可以参考[组合总和2](LeetCode 40 组合总和 II - 回溯解法.md) 去重，设置 last 变量记录上一次的值（这就要求排序使相邻元素在一起）。
for(int i = 0;i <max;i++){
if(loc[i]没用过){
path.push(loc[i])
use[i] =1;
add_path()
path.pop()
use[i] =0;
}
}
错误的
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
vector<int> loc_use;
vector<int> loc_number;
void add_path() {
if (path.size() == loc_number.size()) {
result.push_back(path);
return;
}
int last = 11;
for (int i = 0; i < loc_number.size(); i++) {
if (loc_number[i] == last) {
continue;
}
last = loc_number[i];
if (loc_use[i] == 0) {
path.push_back(loc_number[i]);
loc_use[i] = 1;
add_path();
path.pop_back();
loc_use[i] = 0;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
loc_number = nums;
sort(loc_number.begin(), loc_number.end());
loc_use = vector<int>(nums.size(), 0);
add_path();
return result;
}
};
这里 判断完last 后直接设置 last是不对的。[1,1,2]， 这个就无法正常输出了，
出现错误的原因是 ： 不该在一开始就设置last， 在push后再设置last
代码
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
vector<int> loc_use;
vector<int> loc_number;
void add_path() {
if (path.size() == loc_number.size()) {
result.push_back(path);
return;
}
int last = 11;
for (int i = 0; i < loc_number.size(); i++) {
if (loc_number[i] == last) {
continue;
}
if (loc_use[i] == 0) {
last = loc_number[i];
path.push_back(loc_number[i]);
loc_use[i] = 1;
add_path();
path.pop_back();
loc_use[i] = 0;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
loc_number = nums;
sort(loc_number.begin(), loc_number.end());
loc_use = vector<int>(nums.size(), 0);
add_path();
return result;
}
};