39. 组合总和

39. 组合总和

https://leetcode-cn.com/problems/combination-sum/

第一次解：
回溯，每次减各个数值后的情况
如果最后的值为0表示符合组合要求，<0则提前剪枝
代码：

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

var combinationSum = function(candidates, target) {
    let res = [];
    let len = candidates.length;
    let helper = (currentRes, current) => {
        if(current <= 0) {
            if(current === 0){
                res.push(currentRes);
            }    
            return;
        }
        for(let j = 0; j < len; j++) {
            helper(currentRes.concat(candidates[j]), current-candidates[j]);
        }
    

    }
    helper([], target);
    return res;
};

测试用例：

[2,3,6,7]
7

测试结果：

[[2,2,3],[2,3,2],[3,2,2],[7]]

正确结果:

[[2,2,3],[7]]

发现有重复的数据。

第二次解：
在原来的基础上，先对原数组排序；
排序后，在回溯时上次添加进来的值是否大于本次要减的值，如果是，说明之前已经减过，有重复的解，continue,否则继续回溯。

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

var combinationSum = function(candidates, target) {
    let res = [];
    let len = candidates.length;
    candidates = candidates.sort((p, q) => p-q);
    let helper = (currentRes, current) => {
        if(current <= 0) {
            if(current === 0){
                res.push(currentRes);
            }    
            return;
        }
        for(let j = 0; j < len; j++) {
            if(currentRes.length && (currentRes[currentRes.length-1] > candidates[j])) continue;
            helper(currentRes.concat(candidates[j]), current-candidates[j]);
        }
    }
    helper([], target);
    return res;
};

最后得以通过。