代码随想录算法训练营第二十八天|491.递增子序列

这题是在无法进行排序的情况下如何进行树层去重，思路是每一层都新建一个set容器进行比较

每一树层插入一个数字，就会记录在set中，当这一层再次出现相同数字时，set中的find函数会发现这个数字已经被使用过，跳过该次循环。

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();
}

问题是我在函数外侧建立好set数组，每一层都重新清空可不可以、

uset.clear(); // 到新的一层直接清空
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();
}

 左边是重新建立set，右边是清空set，红色数字是代码执行的顺序

可以看到，右边第4步的set容器继承了第三步的结果，再插入7，容器中只剩下7,4不见了。

本质原因是左边不止一个set容器used，每一层新建的uesd数据都是互相不共通的！不能因为他们的名字一样就认为他们是同一个容器！

如果想右边一样自始至终使用同一个容器的话，在子层清空的时候会丢失父层的信息。

47.全排列 II

首先，每次循环必须从0开始，所以就是同时要进行两次去重

1.为了防止因为重复数字出现重复组合，同一树层不能使用（数字）相同的元素；

2.为了防止同一个数字重复使用，同一树枝不能重复使用相同的元素（这里的相同指的是数字和在nums中的位置同时相同）

树层去重前几天的题已经讲得很明白了，排序——used[i-1]=false几步走就行了，

for (int i = 0; i < nums.size(); i++) {
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }

树枝去重其实挺有意思的，这里的树枝去重和之前的题还不太一样

之前的题是树枝不能重复出现数字相同的元素，这里的条件降低了，只需要不重复出现数字和位置同时相同的元素就可以了（比如说[1,2,2]也可以出现，但是这两个2在nums数组中的位置不一样）

这里排序后我们直接用used[i] 记录每一个位置元素的使用情况，不用used[nums[i]]记录每一个数字的使用情况是因为数字相同的元素是可以重复出现的。位置才是决定树枝去重的关键。

因为条件降低了，所以我们不能再用之前的i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true

进行树枝去重了，用更强的条件会导致丢失满足弱条件的组合的。