40-组合总和II.md

题目描述

组合总和 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]
• ]

分类

中等 数组 回溯

思路

思路 1

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  candidates.sort((x, y) => x - y);
  candidates = candidates.filter(
    (i) => i === target || i + candidates[0] <= target
  );
  const res = [];
  function backTrack(arr, numIndex) {
    if (sum(arr) > target) return true;
    if (sum(arr) === target) {
      res.push([...arr]);
      return true;
    }
    for (let i = numIndex; i < candidates.length; i++) {
      if (i !== numIndex && candidates[i] === candidates[i - 1]) {
        continue;
      }
      arr.push(candidates[i]);
      if (backTrack(arr, i + 1)) {
        arr.pop();
        return;
      }
      arr.pop();
    }
  }
  backTrack([], 0);
  return res;
};
const sum = function (arr) {
  return arr.reduce((total, i) => total + i, 0);
};

• 问题分析
  • 因为题目中有目标和，所以我们先将数组排序，便于进行取值时逐渐逼近目标值。
  • 其次，数组中并不是所有的值都满足我们的需求，我们只需要两种：
    • 单个值时，该值等于目标值；
    • 多个值时，该值 + 最小值 <= 目标值
  • 回溯思路
    • 传入一个暂存数组arr，从数组第一位开始寻找值开始填充arr，存在可以填入的值则填入后继续填充后一位；结束或者不满足则删除arr最后一位，并使用下一个可能条件进行填充。
    • 回溯终止条件：
      • 无结果的终止：arr之和大于目标值
      • 符合预期的终止：arr之和等于目标值
    • 回溯可能路径判断：
      • 从传入的numIndex开始，到数组的长度为止，而且如果值是重复的i !== numIndex && candidates[i] === candidates[i - 1]，则跳过本次循环。