组合总和 II-40

[sl1673495]

给定一个数组 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]
]
示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

和组合总和-39 思路类似，只不过由于不需要考虑同一个元素重复使用的情况，每次的递归的 start 起点应该是 prevStart + 1。

由于数组中可能出现多个相同的元素，他们有可能会生成相同的解，比如 [1, 1, 7] 去凑 8 的时候，可能会用下标为 0 的 1 和 7 去凑 8，也可能用下标为 1 的 1 和 7 去凑 8。

所以在把解放入数组中之前，需要先通过一个唯一的 key 去判断这个解是否生成过，但是考虑到 [1, 2, 1, 2, 7] 这种情况去凑 10，可能会生成 [1, 2, 7] 和 [2, 1, 7] 这样顺序不同但是结果相同的解，这是不符合题目要求的。

所以一个简单的方法就是，先把数组排序后再求解，这样就不会出现顺序不同的相同解了，此时只需要做简单的数组拼接即可生成 key [1, 2, 7] -> "1 ~ 2 ~ 7"。

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
let combinationSum2 = function (candidates, target) {
  let res = []

  if (!candidates.length) {
    return res
  }

  candidates.sort()

  let used = {}

  let helper = (start, prevSum, prevArr) => {
    // 由于全是正整数 所以一旦和大于目标值了 直接结束本次递归即可。
    if (prevSum > target) {
      return
    }
    // 目标值达成
    if (prevSum === target) {
      let key = genKey(prevArr)
      if (!used[key]) {
        res.push(prevArr)
        used[key] = true
      }
      return
    }

    for (let i = start; i < candidates.length; i++) {
      // 这里还是继续从start本身开始 因为多个重复值是允许的
      let cur = candidates[i]
      let sum = prevSum + cur
      let arr = prevArr.concat(cur)
      helper(i + 1, sum, arr)
    }
  }

  helper(0, 0, [])

  return res
}

let genKey = (arr) => arr.join("~")

[cwjbjy]

这个解法，数据一长，力扣就报超时了

[cwjbjy]

var combinationSum2 = function (candidates, target) {
    candidates.sort();
    let res = [];
    function dfs(start, prevSum, prev) {
        if (prevSum > target) return;
        if (prevSum == target) {
            res.push(prev);
            return;
        }
        let used = {};
        for (let i = start, len = candidates.length; i < len; i++) {
            let cur = candidates[i];
            if (used[cur]) continue;
            used[cur] = true;
            dfs(i + 1, prevSum + cur, prev.concat(cur));
        }
    }
    dfs(0, 0, []);
    return res;
};

[sl1673495]

更好的解法：

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
    let res = []
    let path = []
    let total = 0
    candidates.sort((a, b) => a - b)
    let used = new Array(candidates.length).fill(false)
    let helper = (start) => {
        if (total > target) return
        if (total === target) {
            res.push([...path])
            return
        }
        for (let i = start; i < candidates.length; i++) {
            if (used[i - 1] === false && candidates[i - 1] === candidates[i]) continue
            used[i] = true
            total += candidates[i]
            path.push(candidates[i])
            helper(i + 1)
            path.pop()
            used[i] = false
            total -= candidates[i]
        }
    }
    helper(0)
    return res
};