LeetCode 组合总和（/回溯+剪枝）

原题解

题目

约束

题解

不剪枝

class Solution {
public:
    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.emplace_back(combine);
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> combine;
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }
};

剪枝优化

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