leetcode40.组合总和II(去重思路精讲，经典题也可以有困难的思考！)

首先感谢您，打开本文章，一道网上很多题解的一道经典回溯题，能讲出什么花来呢？

看了这篇文章，希望能使您眼前一新。

大概的思路对于一些读者可能很简单，我也简单提一嘴解题思路，因为可能有新读者来看本篇文章。

基本的思路就是和普通求组合总和差不多，多的部分是去重，我们的思路是这样的用一个数组辅助加数据，当满足一定条件时也就是该辅助数组数据和等于target，把辅助数组得到的组合作为答案放入答案数组中，递归函数的思路是：用传进来的start，也就是下一次递归的遍历开始位置开始循环，这样做是为了避免一个数组里取重复数据，然后用一个数组来记录每一个位置是否取过，这个是为了做树层去重。

先讲一下什么树层去重什么是树枝去重？

树层去重就是根据题目的意思，一个答案取过组合答案了，那么后面的组合答案不能使用前面已经得到答案的数字了，也就是说要对后面的组合进行去重，不要让它的内容出现与前面答案相等的数字，树枝去重就是同一个答案里，相等的数字不能出现，本题的意思是要进行树层去重而不是树枝去重，请读者注意。

一定要对数据进行排序，这是最重要的，根据测试用例答案也能知道，虽然第一个测试用例给定的数组两个1是不挨着的，但是答案要求它们是挨着的，不能返回不同的答案顺序，
这就暗示你要排序，其次要进行去重的工作也得排序。

用一个bool数组记录每一个位置，判断是否使用过，但是我们这个数组的用途是判断树层间的去重，递归可以画成一棵树，对树层方面的去重可以避免其他的组合答案，重用前面的组合答案里的数字，这样就能
得到题目要的结果，而树枝之间的去重，和我们本题的思路不同，它更为简单，它是为了避免取到的组合答案里，出现相等的数字。
在i大于0，也就是i不在起始位置之后，我们每次进行判断，如果i与i-1的位置所对应的数据相等，那么查看我们的布尔类型的树层去重数组，如果此时的上一个i的位置也就是i-1位置在该数组中取的是false，那么
认定为树层去重生效，则跳过本次接下来的代码，使i+1。如果i-1位置不在数组中标记为false，并且此时i和i-1位置数字还相等，则说明此时是树枝上的重复，这符合答案要求。
我们每次进来循环，让arr【i】=true，这就使得下一次的递归，不会因为树枝重复而跳出，让回溯之后的arr【i】=false，这是避免树层重复而跳出递归。
因为回溯到的位置，一定是已经递归过的位置，所以把相应位置置为false，是没问题的，它一定就是树层上的重复。
而且回溯并不会马上全部回溯，它会先找到该树层中没有其余的解之后，再向上层回溯，也就是说初步来看，我们深层树层最先回溯，这样的影响也是最小的，
它保证后几个数填数不会重复，你是不是在担心，会不会出现前面重复后面不重复的情况得到target？
别担心，实际不会出现这种情况，因为前面重复后面不重复的数据根本凑不成target，所以它不会停在深层的树层去重，而是继续向上层回溯
向上层回溯之后，回到之前的略靠近最上层的位置，这通常是第二层（第一层是根，相当于不填数字，无法回溯），然后去找其他的解，而此时一开始找数的那些路径已经全部被标记为false
无法查找，也就实现了不会在其他解中找到与前面已找到的数字相同的情况。

实现代码如下

class Solution {
public:
vector<vector<int>>res;
vector<int>path;
 
void back(vector<int>&candidates,int target,int sum,int start,vector<bool>&arr){
    if(sum>target)return ;
    if(sum==target){
        res.push_back(path);return ;
    }
    for(int i=start;i<candidates.size();++i){
        if(i>0&&candidates[i]==candidates[i-1]&&arr[i-1]==true)continue;
        path.push_back(candidates[i]);
        sum+=candidates[i];arr[i]=false;
        back(candidates,target,sum,i+1,arr);
        path.pop_back();sum-=candidates[i];arr[i]=true;
    }
}
    vector<vector<int>> combinationSum2(vector& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<bool>arr(candidates.size(),true);
        back(candidates,target,0,0,arr);
        return res;
    }
};

再来说说为什么初始化arr数组为false，实际上你要是完全相反的写代码判断逻辑，也是可以对的，也就是说一开始全部初始化为true，然后判断树层去重就是上一个位置的去重数组里是否标记为rue，再然后
树枝去重的避免是把它置为false，然后回溯置为true，这样完全相反写也是行得通的，这里主要想说明的不是初始化为true还是false的问题，而是要说明那个中间的判断位置也就是为回溯的部分，有一个修改
arr以避免树枝去重，这个步骤是十分重要的，为什么要特意说这一点呢？
我有一个想法是如果把arr初始化为true，然后判断上一个位置是否为false，回溯时候更改这个标志位为false，来避免树层循环，那是不是就可以节省树枝循环这一步的arr【i】=true了？

实际上是错误的答案，在测试用例【2，2，2】中target=2时候，得到的组合结果有两个且都为【2】。这说明确实树层去重起了作用，但是并没有去重干净。
第一个答案取得是理所应当的，顺其自然的，然后由于sum此时已经==target造成回溯，回溯导致第一个位置2被置false，这样的结果会导致第二个数据2被直接跳过，然后i++，此时再进行判断，然而第二个2
的跳过并不完全是好事，虽然第二个2的跳过完成了树层去重，但是也导致了它没有被置为false，这时候第三个2虽然与第二个2相等，但是无法被去重，这也就导致了为什么会有两个2的结果。
这些推理得出一个结论：不能省略树枝的标志位

那是不是加上就可以了呢？
把arr初始化为true，然后判断上一个位置是否为false，回溯时候更改这个标志位为false，不回溯也就是正常情况还是加上一个arr【i】=true
你会发现加了实际上和没加没有任何区别，还是会报错，确实是因为要附上标志位的问题，但是不是这种初始化为true，但是你树枝去重还是arr【i】=true，这实际上没有发生任何改变。
那是不是arr【i】=false就可以了呢？也不对，回溯置为false，递归也置为false是什么意思？
意思是对树层和树枝进行双重的去重
问题实际上发生在if判断上！if判断树层去重为false进行树层去重还是为true进行树层去重，完全取决于初始化，且该if判断必须与初始化保持一致，才能正确的进行树层去重

也就是说实际逻辑是这样的，初始化为true那么if就是判断true，初始化为false，那if判断false，树枝去重的改变也就是递归之前是把该标志位标成相反的，回溯标成与初始化相同的，只有这一种方法能使答案正确
但是初始化为true还是false，是没关系的，有关系的是if和中间的各个状态如何改变的事情。
结论：树层去重很大一部分取决于if判断，if判断写错了，那你之间代码无论是回溯还是递归为true或者false，都不行。而且递归的那个标志转换不能省略！

---

本文章的精髓在于清晰的介绍了为什么这样写去重逻辑，以及去重数组是否一定要写成false，可以写成其他的吗？以及数组的初始化与里层实现递归逻辑和回溯逻辑的关系，相信已经讲的非常清楚了

本期内容就到这里
如果对您有用的话别忘了一键三连哦，如果是互粉回访我也会做的！

大家有什么想看的题解，或者想看的算法专栏、数据结构专栏，可以去看看往期的文章，有想看的新题目或者专栏也可以评论区写出来，讨论一番，本账号将持续更新。
期待您的关注