跟“去重”相关的题目：
- 三数之和
- 组合之和Ⅱ
- 子集Ⅱ
- 递增子序列
在回溯算法题目中，去重问题分为“树层去重”和“树枝去重”
- 之前组合之和、子集中的去重使用的方法都是先排序，使用prev_pop记录每次在temp中pop出的值，解决的是“树层去重”。因为题目要求的是在当次temp中，是允许有重复元素的（即树枝无需去重）。
LC491. 递增子序列
递增子序列，这道题很明显不能排序。因为对[4, 7, 6, 7]来说，排序后会出现[4, 6, 6, 7]这样的数组，不符合题意。
关于去重的问题，在第一次编码时，就想到了：
- 如果是1、1、2、2、2、5，去重方法跟之前的“子集Ⅱ”一致，先排序，记录pop出值
- 如果是4、6、7、6、7，开始的想法不太正确，看了Carl的视频后，就通透了。访问过第一个6和7后，凡是之后遇到重复的元素，都直接跳过(树层去重)，因为在第一个6的递归搜索中一定会把第二个6后面的元素全部访问一遍了，所以到了第二个6的时候，不需要再劳烦访问后面的，直接跳过即可。
- 为了实现上述的去重，可以使用哈希表（这里用unordered_set比较合适）
- 注意定义的uset，是只记录本层元素是否重复使用，新的一层uset都会重新定义（清空），这就是理解“树层去重”的重点所在。
开始掉坑上去了，这里的终止条件仅仅为if (temp.size() >= 2)，对例子[4, 4, 3, 2, 1]，temp中为[4, 4]时，往后访问3、2、1都不符合>=4，但temp[4, 4]都满足终止条件，所以多次被压入。自己想到的解决办法有：
- 记录上次temp中元素的个数和temp.back()，如果这次两者都相等，则说明出现上述情况，做不压入处理
Carl讲解：自己在做的时候，思维和想法受之前“组合”和“子集”题目的限制，代码中间对nums[i]值的判断，如果 < temp.back()的话，递归的深度还是停留在该层，然后接着遵循for循环去访问下标 i 之后的元素。这样导致的问题是，当前nums[i]不满足>=temp.back()，就去访问了i之后的元素，等到这层递归结束，回溯到上层时，又去访问刚刚的"i"的之后的元素，于是就造成了重复。
所以综上，对例子[4, 4, 3, 2, 1]这种情况，是自己写的代码中 if 处理不够考虑周全。而像Carl哥的题解，是一旦遇到nums[i] < path.back()的情况，直接continue，不再访问该层递归。
////自己的解法
int prev = INT_MIN;
vector<int> temp;
vector<vector<int>> result;
void findSubsequencesLoop(vector<int>& nums, int left)
{
if (temp.size() >= 2)
{
result.emplace_back(temp);
}
for (int i = left; i < nums.size(); i++)
{
bool push_flag = false;
if (prev == nums[i])
{
continue;
}
if (temp.empty() == true || nums[i] >= temp.back())
{
push_flag = true;
temp.emplace_back(nums[i]);
}
findSubsequencesLoop(nums, i + 1);
if (push_flag == true)
{
prev = temp.back();
temp.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums)
{
findSubsequencesLoop(nums, 0);
return result;
}
Carl哥题解：
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
if (path.size() > 1) {
result.push_back(path);
// 注意这里不要加return，要取树上的节点
}
unordered_set<int> uset; // 使用set对本层元素进行去重
for (int i = startIndex; i < nums.size(); i++) {
if ((!path.empty() && nums[i] < path.back())
|| uset.find(nums[i]) != uset.end()) {
continue;
}
uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
LC46. 全排列
我的做法是用unordered_set记录这个数组访问过的元素。
unordered_set<int> uset;
vector<int> temp;
vector<vector<int>> result;
void permuteLoop(vector<int>& nums)
{
if (temp.size() == nums.size())
{
result.emplace_back(temp);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
bool push_flag = false;
if (uset.find(nums[i]) == uset.end())
{
push_flag = true;
temp.emplace_back(nums[i]);
uset.emplace(nums[i]);
}
if (push_flag == true)
{
permuteLoop(nums);
temp.pop_back();
uset.erase(nums[i]);
}
}
}
vector<vector<int>> permute(vector<int>& nums)
{
permuteLoop(nums);
return result;
}
本题，Carl哥中used数组的思想（记录元素的下标即可--因为没排序）
////Carl题解
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) continue; // path里已经收录的元素，直接跳过
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
官方做法：
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// 所有数都填完了
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 动态维护数组
swap(output[i], output[first]);
// 继续递归填下一个数
backtrack(res, output, first + 1, len);
// 撤销操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
LC47. 全排序Ⅱ
这道题不能像上一道题自己的做法一样，不能直接使用unordered_set判断是否跟nums[i]的值有重复的。同时还要进行“树层去重” 。
-
先对nums进行排序
-
使用used数组，代替unordered_set用来记录已经使用过的元素的下标
-
使用之前的prev_pop方式进行“树层去重” ，但跟之前的“组合之和Ⅱ”和“子集Ⅱ”有点不同，这个表现为两个方面：
- 例子：[1,1,2]，因为之前的for循环中int i = left，left在往深层递归时是不断往右移，而“全排序”问题，每次的 i 都是从0开始的，所以如果像开始那样仅仅判断if （prev == nums[i]）的话导致只出现预期结果[[1,1,2],[1,2,1],[2,1,1]]中的第一项，因为[1, 1, 2]弹出第二个"1"时，保存的prev_pop是1，下次递归temp = [1, 2]时想判断下一位"1"时，因为跟prev_pop冲突，所以[1,2,1]就不会被放入结果集。所以加多一个pop_flag标志位来判断出现冲突时，石佛普
- 例子：[0,3,3,3]， if (pop_flag == true && prev == nums[i]) { pop_flag = false; continue; } pop_flag = false; 以上第一版这样写，会导致“树层去重”得不彻底，所以要像下面修改后的，对3个或3个以上的重复元素，连续去重，直到遇到一个不再重复的。
vector<vector<int>> result;
vector<int> temp;
int prev = INT_MIN;
bool pop_flag = false;
void permuteLoop(vector<int>& nums, vector<bool>& used)
{
if (temp.size() == nums.size())
{
result.emplace_back(temp);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (pop_flag == true && prev == nums[i])
{
continue;
}
else if (prev != nums[i])
{
pop_flag = false;
}
if (used[i] == true)
{
continue;
}
temp.emplace_back(nums[i]);
used[i] = true;
permuteLoop(nums, used);
used[i] = false;
prev = temp.back();
temp.pop_back();
pop_flag = true;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums)
{
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
permuteLoop(nums, used);
return result;
}