39

题目

方法一：回溯

var combinationSum = function(candidates, target) {
    const ans=[];
    function dfs(target,arr,idx,num){
        if(num>target)return;
        if(num===target){
            ans.push(arr);
            return;
        }
        if(idx>=candidates.length)return;
        dfs(target,arr,idx+1,num);
        dfs(target,[...arr,candidates[idx]],idx,num+candidates[idx]);
    }
    dfs(target,[],0,0);
    return ans;
};

方法二：回溯

var combinationSum = function(candidates, target) {
    let ans=[];
    function dfs(target,comb,idx){
        if(idx===candidates.length)return;
        if(target===0){
            ans.push(comb);
            return;
        }
        dfs(target,comb,idx+1);
        if(target-candidates[idx]>=0){
            dfs(target-candidates[idx],[...comb,candidates[idx]],idx);
        }
    }
    dfs(target,[],0);
    return ans;
};