leetcode-0039 组合总数

[GuoLizhi]

回溯

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b);
    dfs(candidates, target, 0, [], result);
    return result;
};

var dfs = function (candidates, target, begin, path, result) {
    if (target === 0) {
        result.push([...path]);
        return;
    }
    for (let i = begin; i < candidates.length; i++) {
        if (target - candidates[i] < 0) {
            break;
        } 
        path.push(candidates[i]);
        dfs(candidates, target - candidates[i], i, path, result);
        path.pop();
    }
}