39. 组合总和

39. 组合总和

很慢的dfs

class Solution {
public:
    vector<vector<int>> res;
    vector<int>nums;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        nums=candidates;
        dfs(0,vector<int>(),target);
        return res;
    }
    
    void dfs(int u,vector<int> path,int sum){
        if(u>=nums.size()){
            if(sum==0) res.push_back(path);
            return;
        }
        
        // 不选
        dfs(u+1,path,sum);
        // 选1 2 3 ...个 直到不满足sum>=0
        while(sum-nums[u]>=0){
            sum-=nums[u];
            path.push_back(nums[u]);
            dfs(u+1,path,sum);
        }
    }
};