题解 | #加起来和为目标值的组合#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
                //剪枝，需要排序
        sort(nums.begin(),nums.end());
        dfs(res, path, 0, 0, target, nums);
        return res;
        // write code here
    }
    void dfs(vector<vector<int>>& res, vector<int>& path, int index,
            int cur_sum, int target, vector<int>& nums){
        if(cur_sum==target){
            res.push_back(path);
            return;
        }//剪枝需要排序
        for(int i=index; i<nums.size()&& cur_sum+nums[i]<=target; i++){
            path.push_back(nums[i]);
            cur_sum += nums[i];
            dfs(res, path, i, cur_sum, target, nums);
            cur_sum -= nums[i];
            path.pop_back();
            
        }
    }
};