40. 组合总和 II

// 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的每个数字在每个组合中只能使用一次。
// 说明：
// 所有数字（包括目标数）都是正整数。
// 解集不能包含重复的组合。
var combinationSum2 = function(candidates, target) {
  if (candidates.length === 0) return [];
  candidates = candidates.sort((a, b) => a - b);
  const totalArr = [];

  function dfs(arr, res, start) {
    for (let i = start; i < candidates.length; i++) {
      const item = candidates[i];
      if (i - 1 >= start && item === candidates[i - 1]) continue;
      const sum = res + item;
      if (sum === target) {
        totalArr.push([...arr, item]);
        break;
      } else if (sum > target) {
        continue;
      } else {
        dfs([...arr, item], sum, i + 1);
      }
    }
  }

  dfs([], 0, 0);

  return totalArr;
};

console.log(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8));
console.log(combinationSum2([2, 5, 2, 1, 2], 5));