组合问题系列

要牢记一句：回溯问题抽象为树形结构，for 循环横向遍历，递归纵向遍历，回溯不断调整结果集。

组合总和

给你一个 无重复元素 的整数数组candidates和一个目标整数target，找出 candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为target的不同组合数少于 150 个。

代码实现

var combinationSum = function (candidates, target) {
  const res = [];
  // const path = []
  const dfs = (path, start) => {
    const sum = path.reduce((a, b) => a + b, 0);
    if (sum === target) {
      res.push(path);
      return;
    }
    if (sum > target) {
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      dfs(path.concat(candidates[i]), i);
    }
  };
  dfs([], 0);
  return res;
};

组合总和 II

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

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

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

代码实现

var combinationSum2 = function (candidates, target) {
  const res = [];
  candidates.sort((a, b) => a - b);
  const dfs = (start, path) => {
    const sum = path.reduce((a, b) => a + b, 0);
    if (sum === target) {
      res.push([...path]);
      return;
    }
    if (sum > target) return;
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      if (sum + candidates[i] > target) break;
      path.push(candidates[i]);
      dfs(i + 1, [...path]);
      path.pop();
    }
  };
  dfs(0, []);
  return res;
};