JavaScript - 组合求和2(回溯法)

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:

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

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
 [1, 7],
 [1, 2, 5],
 [2, 6],
 [1, 1, 6]
]

完整代码:

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    let arr = candidates.sort((m, n)=> m - n);
    let res = [];

    function def(nums, path, target) {
        for (let i = 0; i < nums.length; i++) {
            let curPath = [...path, nums[i]];
            let curTarget = target - nums[i];

            if(i > 0 && nums[i - 1] === nums[i]) continue;
            if (curTarget === 0) res.push(curPath);
            if (curTarget >= nums[i]) {
                def(nums.slice(i+1), curPath, curTarget);
            };
        }
    }

    def(arr, [], target);
    return res;
};

你可能感兴趣的