39. 组合总和、40. 组合总和 II

39. 组合总和

题目描述：

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

解答：

这个还是很简单的，但是有个小坑。

先看到这个题，懵了一下，这要有0咋办，后来仔细一看发现有范围限制

这个范围限制其实也就是限制了for循环的循环次数（也就是树的宽度）

树的深度——和大于等于时抵达了叶子节点

树的宽度——因为可以重复取，那就直接是candidates数组的长度 

但是有个小坑，如果直接这么搜索，如何区分（2，2，3）和（3，2，2）和（2，3，2）？

这个其实只需要对每次循环的起始位置加以限制即可，如下图所示。前面的已经搜索结束了，只需要搜索当前数往后的组合即可。

回溯三部曲：

（1）参数和返回值：

        candidates数组、target、一个sum记录当前的和、start记录下次的起始位置

        无需返回值，直接将result和path记录为全局变量即可。

（2）终止条件：

        当sum大于或者等于target时就终止。

（3）内部处理逻辑：

        先将当前节点更新进path，然后更新sum，递归。

        回溯，复原sum和path

代码实现：

class Solution {
public:
    vectorint>>result;
    vector<int>path;
    void backTrace(vector<int>& candidates, int target, int sum, int start){
        if(sum >= target){
            if (sum == target)
                result.push_back(path);
            return;    
        }
        for (int i = start; i < candidates.size(); i++){
            path.push_back(candidates[i]);
            sum += candidates[i];
            backTrace(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vectorint>> combinationSum(vector<int>& candidates, int target) {
        backTrace(candidates, target, 0, 0);
        return result;
    }
};

剪枝优化：

这个地方其实可以用回溯中经常用的方法

先排序再剪枝

因为排序后的序列，有大小的相关性，更容易根据要求进行剪枝

回到本题，排序后由小到大，当遇到小的数字递归已经大于等于target时，就无需继续进行for循环了，剪枝即可，如下图所示：

代码实现：

class Solution {
public:
    vectorint>>result;
    vector<int>path;
    void backTrace(vector<int>& candidates, int target, int sum, int start){
        if(sum >= target){
            if (sum == target)
                result.push_back(path);
            return;    
        }
        for (int i = start; i < candidates.size() && sum + candidates[i] <= target; i++){
            path.push_back(candidates[i]);
            sum += candidates[i];
            backTrace(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vectorint>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); 
        backTrace(candidates, target, 0, 0);
        return result;
    }
};

40. 组合总和 II

题目描述：

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

解答：

先排序再进行回溯处理。

这道题和上一道很相似，但是主要有两处不同：

        （1）每个数只能被选用一次

        （2）有重复元素

对于第一处不同很简单，让每次递归寻找从i+1开始即可

对于第二处相对来说比较复杂，这个地方其实是要防止同一层的元素重复找比如：

放到树里边也就是要防止同一层的相邻节点相同导致的重复搜索。

相邻节点相同很容易判断：if（candidates[i] == candidates[i-1])

只有这一个条件会导致不同层的节点被去除，如下图所示：

那同一层应该怎么表示呢？  i > start

因为往深了走i一定是等于start的，只有遍历同一层时i才会大于start。

代码实现：

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