leetcode39 组合总和

这道题想到的就是dfs，在累加的和大于或等于target时到达递归树的终点。

代码如下：

class Solution {

public:

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

        int r=candidates.size()-1;

        vector<vector<int>> res;

        for(int i=r;i>=0;i--){

            vector<int> tmp;

            int sum=0;

            dfs(candidates, tmp, res, target, i, sum);

        }

        return res;

    }

    void dfs(vector<int>& candidates, vector<int>& tmp, vector<vector<int>>& res, int target,int id,int& sum){

        sum+=candidates[id];

        tmp.push_back(candidates[id]);

        if(sum>=target){

            if(sum==target) res.push_back(tmp);

            sum-=candidates[id];

            tmp.pop_back();

            return;

        }

        for(int i=id;i>=0;i--){

            dfs(candidates,tmp,res,target,i,sum);

        }

        tmp.pop_back();

        sum-=candidates[id];

    }

};

巴特西

leetcode39 组合总和

最新文章

热门文章