39. 组合总和

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates,int target,int startIndex)
    {
        if(target<0)return;
        if(target==0)
        {
           result.push_back(path);
            return; 
        }
        for(int i = startIndex;i<candidates.size();i++)
        {
            path.push_back(candidates[i]);
            // 关键点:不用i+1了，表示可以重复读取当前的数
            //从与上一层循环相同的位置开始
            backtracking(candidates,target-candidates[i],i);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,target,0);
        return result;
    }
};

剪枝

对数组进行排序，再剪枝

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates,int target,int startIndex)
    {
        if(target==0)
        {
           result.push_back(path);
            return; 
        }
        //target-candidates[i]>=0才进入循环
        for(int i = startIndex;i<candidates.size()&&target-candidates[i]>=0;i++)
        {
            path.push_back(candidates[i]);
            backtracking(candidates,target-candidates[i],i);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0);
        return result;
    }
};