力扣39题 组合总和

类型：回溯算法

无重复元素

重点：同一个数字可以无限制重复选取，但是有总和的限制，所以间接的也就是有个数的限制。

1.递归函数参数

result存放结果集，数组path存放符合条件的结果。集合candidates和目标值target，需要使用startindex来控制循环的起始位置，对于组合问题，什么时候用startindex？

如果一个集合来求组合的话，就需要使用startindex，如果是多个集合取组合，各个集合之间相互不影响，就不用startindex，为了防止出现重复的组合。

2.递归终止条件

sum大于等于target

3.单层搜索的逻辑

单层for循环依然是从startindex开始，搜索candidates集合。

class Solution {

public:

    vector<vector<int>>result;

    vector<int>path;

    void backtracing(vector<int>&candidates,int target,int sum,int startIndex){

        if(sum>target){

            return;

        }

        if(sum==target){

            result.push_back(path);

            return;

        }

        for(int i=startIndex;i<candidates.size();i++){

            sum += candidates[i];

            path.push_back(candidates[i]);

            backtracing(candidates,target,sum,i);

            sum -= candidates[i];

            path.pop_back();

        }

    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        result.clear();

        path.clear();

        backtracing(candidates,target,0,0);

        return result;

    }

};