组合总和

[JesseZhao1990]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    
    var res = [];
    function dfs(candidates,target,arr,j){
        if(target<0){
            return;
        }
        if(target===0){
            res.push([...arr]);
            return;
        }
        for(var i=j;i<candidates.length;i++){
            arr.push(candidates[i]);
            dfs(candidates,target-candidates[i],arr,i);
            arr.pop();
        }
    }
    dfs(candidates,target,[],0);
    return res;
    
};

解题思路

递归终止的条件就是target等于零，还有一个问题是如何确保收集的结果不重复，这里需要进行剪枝操作

LeetCode原题地址：https://leetcode-cn.com/problems/combination-sum/description/