题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html

视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ

1.这个题的和昨天做的组合的题很像，只是剪枝的部分有和昨天不同的地方，第一个sum + candidates[i] <= target就是这个在循环过程中的剪枝，在循环过程中由于对于数组已经升序排序过了，所以当出现这个条件的时候无需遍历后面的数据，而且本题可以使用重复的元素所以，本题的startIndex还是i而不是i + 1。

CPP

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