LeetCode - 40 組合總和 II

目錄

題目來源

題目描述

示例

提示

題目解析

算法源碼

題目來源

40. 組合總和 II - 力扣（LeetCode）

題目描述

給定一個候選人編号的集合 candidates 和一個目标數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中隻能使用 一次 。

注意：解集不能包含重複的組合。 

示例

輸入: candidates = [10,1,2,7,6,1,5], target = 8,

輸出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

輸入: candidates = [2,5,2,1,2], target = 5,

輸出: [ [1,2,2], [5] ]

提示

• 1 <= candidates.length <= 100

• 1 <= candidates[i] <= 50

• 1 <= target <= 30

題目解析

本題的難點在于，輸入數組中存儲值重複的元素，這樣必然會産生重複的組合，但是題目要求結果中不能存在重複的組合。

比如 candidates = [1,1,2], target = 3，則存在如下組合

可以發現有兩個重複的12組合。

此時避免重複有兩種做法，一種是從根源去重，即對candidates去重，但是去重前需要統計重複值的次數

另一種去重政策是，廣度for循環周遊時，檢查candidate[i]是否和candidate[i-1]相同，若相同，則candidate[i]可以提前結束，不需要進入遞歸流程，因為這樣隻會産生重複的組合

算法源碼

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
const result = []
var combinationSum2 = function(candidates, target) {
    result.length = 0

    let count = {}
    candidates.forEach(ele => {
        count[ele] ? count[ele]++ : (count[ele] = 1)
    })

    dfs([...new Set(candidates)].sort((a,b)=>a-b), count, target, 0, [])
    return result
};

function dfs(candidates, count, target, index, path) {
    if(target <= 0) {
        if(target === 0) result.push([...path])
        return
    }

    for(let i=index; i<candidates.length; i++) {
        if(candidates[i] > target) break;

        if(count[candidates[i]] > 0) {
            path.push(candidates[i])
            count[candidates[i]]--
            dfs(candidates, count, target - candidates[i], i, path)
            count[candidates[i]]++
            path.pop()
        }
    }
}
           

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

var combinationSum2 = function(candidates, target) {
    candidates.sort((a,b) => a - b)

    const res = []
    dfs(candidates, target, 0, 0, [],  res)
    return res
};

function dfs(candidates, target, index, sum, path, res) {
    if(sum > target) return
    if(sum === target) return res.push([...path])

    for(let i=index; i<candidates.length; i++) {
        if(i > 0 && candidates[i] === candidates[i-1]) continue
        path.push(candidates[i])
        dfs(candidates, target, i+1, sum + candidates[i], path, res)
        path.pop()
    }
}