慢慢刷题有点熟练了也开始做一些以前不会做的题目，这就有一题叫做 组合总和的问题

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

可以分析一下题目，首先这是一个无重复数字的数组，所以可以尽情放飞自我，一开始看到这个题目我立刻想到了递归回溯，因此代码很快就瞎写出来

class Solution {
public:   
 vector<vector<int>> result;              //储存结果
void backTrace(vector<int>& candidates,int target,vector<int> now,int sum)
{
    if(sum==target)                       //如果总和等于目标，将当前容器添加到结果中
    {
        result.push_back(now);
        return;
    }
    if(sum>target)                         //如果总和大于目标，直接返回
    return;
    for(int i=0;i<candidates.size();i++)   //依次对所有内容进行插入尝试
    {
        now.push_back(candidates[i]);      //插入元素
        backTrace(candidates,target,now,sum+=candidates[i]);                                      //调用
        now.pop_back();                    //弹出元素
        sum-=candidates[i];           
    }
}
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> now;
        backTrace(candidates,target,now,0);
        return result;
    }
};

结果出来后却跟预期结果有所出入，内容是对了，但是却有赘余

可以看出来第一个结果[2,2,3]而我的结果中多了两个，相当于给[2,2,3]来了一次全排列，，因为题目要求解集不能包含重复的组合，因此这样肯定不行

解决方法

在参考了LeetCode的官方题解后，我注意到了一个词

剪枝

看到他的那张图，我立刻明白了，这题中需要运用到剪枝，将多余的结果剪掉，与其说是剪掉不如说就是避免重复结果的产生

题解中是这样说的

• 在搜索的时候需要设置搜索起点的下标begin，下一层的节点从这个搜索起点开始搜索
• 在搜索起点begin之前的数因为以前的分支搜索过了，所以一定会产生重复

瞬间理解了要表达的意思，并修改了代码

AC代码

class Solution {
public:
 vector<vector<int>> result;
//在函数中添加了begin变量用于剪枝
void backTrace(vector<int>& candidates,int target,vector<int> now,int sum,int begin)
{
    if(sum==target)
    {
        result.push_back(now);
        return;
    }
    if(sum>target)
    return;
//从给定的begin开始搜索，以避免产生重复组合
    for(int i=begin;i<candidates.size();i++)
    {
        now.push_back(candidates[i]);
        backTrace(candidates,target,now,sum+=candidates[i],i);
        now.pop_back();
        sum-=candidates[i];
    }
}
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> now;
        backTrace(candidates,target,now,0,0);
        return result;
    }
};

总结

运行用时和内存消耗的结果不是特别好，只战胜了百分之十几的人，不过AC就好，而且还学到了新知识，以后遇到类似问题就能迎刃而解了
话说之前好像做到过类似的题目没做出来，秒回去做题

Q.E.D.