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

給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ,找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。
說(shuō)明:

  • 所有數(shù)字(包括目標(biāo)數(shù))都是正整數(shù)。
  • 解集不能包含重復(fù)的組合。

示例 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;
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書(shū)系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容