40.组合总和II

本题来说还是遇到了较多的问题的，一一列举记录一下：
1 c++的sort方法不会用，写成了sort(candidates);，但实际上正确的写法是sort(candidates.begin(), candidates.end());，也就是说要传两个迭代器而不是整个vector。

2 在写循环逻辑的时候写成了：

while(candidates[i] == candidates[startindex]){
    i++;
}

但实际正确的逻辑是：

if (i > startindex && candidates[i] == candidates[i - 1]) continue;

为什么第一种是对的，第二种就是错的呢？

第一种实际上存在两个问题：
1 我用while循环找到第一个不同的元素，但其实外面还嵌套了一层for循环，在下一个循环的时候还会++，导致跳过一个不同的元素。

2 不应该与candidates[startindex]而应该是与candidates[i]进行比较，这是因为：startindex只是这个for循环的起始节点，但是在后续的for循环当中，也需要进行去重操作，如果与startindex进行比较的话，相当于只与开头的元素进行比较，在逻辑上是错的。

所以最终补全了逻辑的for循环其实得这么写：

        for(int i=startindex; i<candidates.size();){
            // if (i > startindex && candidates[i] == candidates[i - 1]) continue;
            path.push_back(candidates[i]);
            comb(candidates, target - candidates[i], i+1, result, path);
            path.pop_back();
            int p = 0;
            int current = candidates[i];
            while(i+p <candidates.size() && candidates[i+p] == current){
                p++;
            }
            if(p > 0){
                i += p;
            }
            else{
                i += 1;
            }
        }

在这个逻辑当中，相当于去掉了有重复元素的时候的自动++操作，并且也正确的将比较对象调成了candidates[i]。

相比之下其实卡哥的代码就简单很多了，首先是只和前一个元素进行比较，不用纠结到底是startindex还是i，其次是每次只会在满足条件时跳过当前循环，不会像我一样算半天需要跳过几个循环，然后跳错，是负担较低且好写的写法。至于我为什么没想到，是因为这种去重逻辑其实正着想还挺难的（个人认为），看到代码之后倒推反而是好理解的。

卡哥解析里面那个同一树层什么的给我看挺懵逼的，从代码倒退回去讲的话，其实就是相同的数字第二次出现，其实就已经重复了，因为它的上一个元素不取它这一个其实就和从它这里开始，得到的结果是一样的。那所以此时需要判断两件事：

1 现在的这个元素并非起始元素，也就是i>startindex

2 此时的元素是第二次及以上出现，也就是和前一个元素相等了

满足上述的两个条件之后，执行跳过逻辑，最终写出来的代码如下。

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        int startindex = 0;
        vector<vector<int>> result;
        vector<int> path;
        comb(candidates, target, startindex, result, path);
        return result;
    }
    void comb(vector<int>& candidates, int target, int startindex, vector<vector<int>>& result, vector<int>& path){
        if(target == 0){
            if(!path.empty()){
                result.push_back(path);
            }
            return ;
        }
        else if(target < 0){
            return ;
        }
        for(int i=startindex; i<candidates.size();){
            if (i > startindex && candidates[i] == candidates[i - 1]) continue;
            path.push_back(candidates[i]);
            comb(candidates, target - candidates[i], i+1, result, path);
            path.pop_back();
            int p = 0;
            int current = candidates[i];
        }
    }
};

131.分割回文串