回溯之 组合类问题

 一、起点，startindex / index?

1、什么时候用startindex，什么时候不用？

ans：一般在一个集合里反复操作，用。在多个独立集合里，不能用。

2、backtracking(nums,sum,i)。和backtracking(nums,sum,i+1)理解区别？

ans：i表示，在每一层的开始，往深处递归，都可以再选自身。就是允许有重复的值

i+1表示，在每一层开始，往深处递归时，都得在自身基础上往前走一个。就是不允许取自身

3、何时可以不在终止条件里return

• 树中有符合的元素，加入到res中，但是下面可能还有符合的。所以不用return，遍历结束也会return。一般子集问题。
• 答案只出现在叶子节点。一般是组合，切割问题。 

二、去重逻辑

可以从两个维度考虑去重：1、树枝去重。2、树层去重。

1、树枝去重：比如(1,1,2)，向下递归的时候，如果开始用第二个1，发现第一个1用过了，就continue了，会漏掉112，这个结果(题目不允许重复使用一个位置上的相同元素) used[i - 1] == true，说明同一树枝candidates[i - 1]使用过 2、树层去重:(1,1,2)，想右遍历的时候，如果遍历到第二个1，发现第一个1使用过(但是used是false，是由于递归回溯的时候，又初始化了)，又因为是排过序的，所以第二个1之后遍历到的结果，肯定已经被第一个1包含了，即再取就重复了。

used[i - 1] == false，说明同一树层candidates[i - 1]使用过.

2、树层去重:(1,1,2)，想右遍历的时候，如果遍历到第二个1，发现第一个1使用过(但是used是false，是由于递归回溯的时候，又初始化了)，又因为是排过序的，所以第二个1之后遍历到的结果，肯定已经被第一个1包含了，即再取就重复了。
used[i - 1] == false，说明同一树层candidates[i - 1]使用过。

1、used标记数组(通用版)

!!!子集类问题去重一定要先排序!!!

1、记录每个下标的元素是否被使用过，仅在一层递归时，会变化，当回溯后(返回上一层，会被初始化)。

注意：why定义全局变量，而不像set一样是局部的（可以局部），主要还是逻辑不一样。先排好序的used是判断位置，而set是判断元素值。保证了树枝可重复，树层不重复。

2、第二种去重逻辑

得先排序

if(i > startindex && candidates[i] == candidates[i-1])
i < startindex表示深度递归，往下递归。
i > startindex 表示同一层级的遍历。以第二层为例：假设第二层的第一个元素深度递归完了之后，i++,遍历第二层的第二个元素，此时startindex并没有变化，还是第一层传上来的0+1=1,但是i已经变成2了，如果和前面一个元素相同，就直接略过了。

3、第三种去重(set)

unordered_setuset;

注意：set不能定义到全局变量，因为，设定的set是管理记录某一个节点下面的同一层。定义到全局变量，就是记录整个树，包括树枝和树层。可得，第一个图已经记录了2，到下一层就不会再选2了。导致错误。而如果是局部set，到第二个时，会重新设一个set来记录，保证了树枝上的可重复选取值相同但位置不同的元素。所以也不能同used一样 insert 和 erase。

使用set去重，set不用参与到回溯代码。因为会在每一层重新定义一个set。set只针对于每一层。

如果范围小，可直接用数组，省时省力。

    result.push_back(path);
        unordered_set<int> uset;
        for (int i = startIndex; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

4、易错点

• used局部变量会错误：每到下一层，刚push的元素位置used[i]=0，意味着到下一层时，又从第一个开始选，树枝上会一直取第一个。
• set全局变量会错误：模拟used 的insert 和 erase，但是set是全局，记录了树枝和树层 一整棵树。向下递归是，可能d不到叶子节点。
• 使用used 或者 i>startindex前得排序。

5、总结： 

• 如果需要对nums先进行排序，直接推荐 i > startindex 或者 used或者set。set也需要事先排序！！！  
• 如果根据题目的意思，不能先对nums进行排序，直接使用set去重。

三、剪枝

在求和问题中，排序之后加剪枝是常见的套路！

ps：

子集是收集树形结构中树的所有节点的结果。

组合、分割问题是收集树形结构中叶子节点的结果。