[数据结构与算法]LeetCode39.40组合总和（dfs+回溯）

39.题目描述（来源LeetCode）

?思路：像这种求可行解的一般会想到要用回溯算法，回溯的过程记录可行解，不合适就回退一步，换一条道继续搜，继续回溯，对于每一个数，在每次搜索的时候有两种情况，加入可行解数组和不加入。搜索结束条件1.当加入可行解数组的和等于target的时候，2.当遍历完数组的时候

代码实现C++：?

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> num;//存放每一次回溯的可行解
        vector<vector<int>> res;//所有可行解
        sort(candidates.begin(),candidates.end());//注意，一定要是有序数组，不然在剪枝的过程会漏掉可行解
        dfsback(candidates,num,res,target,0);
        return res;
    }
    void dfsback(vector<int>& candidates,vector<int>& num,vector<vector<int>>& res,int target,int start){
        if(target==0){//当target==0说明该次搜索的可行解是ok的
            res.push_back(num);
            return;
        }
        for(int i=start;i<candidates.size();i++){//每次搜索从start开始，因为每一组可行解要是唯一的，如果每次都从0开始遍历+回溯，就会像排列组合一样，有许多重复的可行解
            if(target-candidates[i]>=0){
                num.push_back(candidates[i]);
                dfsback(candidates,num,res,target-candidates[i],i);//开始下一次搜索，还是从i开始，表示将该数继续加入可行解，如果不满足，在回溯的过程会将该数弹出，一般dfs+回溯的代码上下对称哦
                num.pop_back();
            }else{
                break;
            }
        }
    }
};

升级版： 40.无重复数字的可行解

?思路：无重复数字，意味着每个数字只有一种情况，加入或者不加入可行解，但是，我们要在先判断该数在数组里是否重复，有一个很好的办法就是排序，让每一个元素与前面一个元素比较是否相等就可以排除重复元素。

代码实现C++：

class Solution {
public:
        vector<vector<int>> res;//存最后的可行解组成的数组
        vector<int> num;//存每一次遍历的可行解
        vector<int> candidates;//数组
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        this->candidates=candidates;
        dfsback(0,target);//
        return res;
    }
    void dfsback(int start,int target){//start每次搜索的起始位置和target目标值
        if(target==0){
            res.push_back(num);
            return;
        }
        for(int i=start;i<candidates.size()&&target-candidates[i]>=0;i++){
            if(i>start&&candidates[i]==candidates[i-1]){//i>start是用来每次至少加入重复元素一个的，比如12224 在从第二个2开始遍历的时候，我们之加入一个2，但如果没有i>start限制，我们就无法加入当前的在原数组中有重复的元素了
                continue;
            }
            num.push_back(candidates[i]);
            dfsback(i+1,target-candidates[i]);//只有一种情况就是加入该元素并搜索下一个位置
            num.pop_back();
        }
    }
};

今日刷题任务完成啦~被回溯折磨的一天（欢迎大家在评论区交流哦！！）