★LeetCode(39)——组合总和(JavaScript)

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

示例2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    
};

个人解法

大佬思路:回溯算法 + 剪枝(Python 代码、Java 代码)

var combinationSum = function(candidates, target) {
    var result = [];

    function digui(target , arr){
        for(var i = 0; i < candidates.length; i++){
            if(target >= candidates[i]){
                var arr2 = [...arr];
                arr2.push(candidates[i]);
                digui(target - candidates[i] , arr2);
            }
        }
        if(target === 0){
            result.push([...arr]);
        }
        return ;
    }

    digui(target , []);

    //result有重复的的组合,进行去重
    for(var i = 0; i < result.lengtg; i++){
        result[i].sort((a,b) => a - b);
        result[i] = result[i].join("-");
    }
    result = [...new Set(result)];
    for(var i = 0; i < result.lengtg; i++){
        result[i] = result[i].split("-");
    }

    return result;
};
上一篇:leetcode-40


下一篇:leetcode 组合总和(Java)