31_回溯_40. 组合总和 II .md

-- 回溯 - mid 点击直达力扣

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

 

示例 1:

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

// 本题的难点在于集合有重复的元素(eg:[1,2,2]),
// 但不能有重复的组合(eg:[1,2,2],[1,2,2])
// 换句话说:在树中,同一层的元素不能重复(宽度)
// 树探索深度的过程中可以重复(深度)
// 在回溯中,for循环控制树的宽度,递归控制树的深度.
let result = []
let path: number[] = []
function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b)
    result = []
    bacTracking(target, 0, candidates)
    return result
};
function bacTracking(sub: number, startIndex: number, candidates: number[]): void {
    if (sub < 0) { return }
    if (sub === 0) {
        result.push([...path])
        return
    }
    // 去重:
    //      每次回溯都调用自己,重置flag,故在集合中可以得到重复的集合.
    //      当回退时,flag为调用栈中所记录的元素,故无法得到重复的组合.
    let flag = -1
    for (let i = startIndex; i < candidates.length; i++) {
        if (flag === candidates[i]) {
            continue
        }
        flag = candidates[i]
        sub -= candidates[i]
        path.push(candidates[i])
        bacTracking(sub, i + 1, candidates)
        sub += candidates[i]
        path.pop()
    }
}