40 组合总和 II

给定一个候选人编号的集合 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] ]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]

function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);
    const n = candidates.length;
    const ans = [];
    const path = [];
    function dfs(i, left) {
        // 所选元素之和恰好等于 target
        if (left === 0) {
            ans.push([...path]);
            return;
        }

        // 没有可以选的数字
        if (i === n) {
            return;
        }

        // 所选元素之和无法恰好等于 target
        const x = candidates[i];
        if (left < x) {
            return;
        }

        // 选 x
        path.push(x);
        dfs(i + 1, left - x);
        path.pop(); // 恢复现场

        // 不选 x，那么后面所有等于 x 的数都不选
        // 如果不跳过这些数，会导致「选 x 不选 x'」和「不选 x 选 x'」这两种情况都会加到 ans 中，这就重复了
        i++;
        while (i < n && candidates[i] === x) {
            i++;
        }
        dfs(i, left);
    }
    dfs(0, target);
    return ans;

};

为了方便跳过相同元素和剪枝，在递归前，把 candidates 从小到大排序。

用 dfs (i,left) 来回溯，设当前枚举到 candidates [i]，剩余要选的元素之和为 left，按照选或不选分类讨论：

选 candidates [i]：递归到 dfs (i+1,left−candidates [i])。不选 candidates [i]：跳过后续所有等于 candidates [i] 的数，递归到 dfs (i ,left)，其中 [i,i−1] 中的数都相同。如果不跳过这些数，设 x=candidates [i], x =candidates [i+1]，那么「选 x 不选 x 」和「不选 x 选 x 」这两种情况都会加到答案中，这就重复了。递归边界：

如果 left=0，说明所选元素之和恰好等于 target，把 path 加入答案，返回。如果 i=n，没有可以选的数字，返回。如果 left<candidates [i]，由于后面的数都比 left 大，所以 left 无法减成 0，返回。递归入口：dfs (0,target)。

40 组合总和 II ​

40 组合总和 II