学习记录：js算法（八十二）：组合总和

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3：
输入: candidates = [2], target = 1
输出: []

思路一

function combinationSum(candidates, target) {const res = [];const backtrack = (path, sum, startIndex) => {if (sum === target) {res.push([...path]);return;}if (sum > target) {return;}for (let i = startIndex; i < candidates.length; i++) {path.push(candidates[i]);sum += candidates[i];backtrack(path, sum, i); // 注意这里是i，允许重复选取同一个元素path.pop();sum -= candidates[i];}};backtrack([], 0, 0);return res;
}

讲解
这道题目可以通过使用回溯算法（Backtracking）来解决。回溯算法是一种通过试探搜索（试错法）来寻找所有可能的解决方案的算法。

1. 初始化：创建一个空的路径数组path来存储当前的组合，以及一个空的结果数组res来存储所有有效的组合。
2. 递归函数：定义一个递归函数backtrack，它接受以下参数：
   ○ 当前路径path，
   ○ 当前路径的和sum，
   ○ 下一个开始搜索的索引startIndex。
3. 基本结束条件：如果当前路径的和sum等于target，将当前路径path拷贝一份加入结果数组res，然后返回。
4. 剪枝条件：如果当前路径的和sum大于target，直接返回，不再继续探索。
5. 回溯过程：对于startIndex到数组末尾的每一个数字，执行以下操作：
   ○ 将当前数字添加到路径path中，并更新路径的和sum。
   ○ 递归调用backtrack函数，传递更新后的path、sum和下一个开始搜索的索引。
   ○ 回溯，即将当前数字从路径path中移除，并恢复路径的和sum。
6. 开始回溯：调用backtrack函数，传入初始的path、sum和startIndex。
7. 返回结果：最后返回结果数组res。

思路二

var combinationSum = function (candidates, target) {const dp = Array.from({ length: target + 1 }, () => []);dp[0] = [[]]; // 目标为0时，只有一种组合：空数组for (const num of candidates) {for (let i = num; i <= target; i++) {for (const combination of dp[i - num]) {dp[i].push([...combination, num]); // 添加当前数字}}}return dp[target];
};

讲解

1. 定义函数：combinationSum 是一个接受两个参数的函数，candidates 是可选的数字数组，target 是我们想要达到的目标和。
2. 创建动态规划数组：dp 是一个二维数组，其中 dp[i] 存储所有和为 i 的组合。我们初始化一个长度为 target + 1 的数组，每个元素都是一个空数组。
3. 初始化基例：dp[0] 被初始化为包含一个空数组的数组，表示和为 0 的组合是唯一的，即不选任何数字。
4. 循环：
   • 外层循环：遍历每个候选数字 num。
   • 中层循环：从 num 开始，遍历到 target。这是因为我们只需考虑从 num 开始的目标值，因为小于 num 的目标值无法包含 num。
   • 内层循环：遍历 dp[i - num] 中的每个组合。dp[i - num] 表示在目标值为 i - num 时的所有组合。
     • 组合构建：对于每个组合，我们创建一个新的组合，将当前数字 num 添加到其中，并将其推入 dp[i] 中。
5. 返回结果：最后，函数返回 dp[target]，即所有和为 target 的组合。

思路三

var combinationSum = function (candidates, target) {const result = [];const stack = [{ combination: [], remaining: target, start: 0 }];while (stack.length) {const { combination, remaining, start } = stack.pop();if (remaining === 0) {result.push(combination);continue;}for (let i = start; i < candidates.length; i++) {if (remaining < candidates[i]) continue;stack.push({ combination: [...combination, candidates[i]], remaining: remaining - candidates[i], start: i });}}return result;
};

讲解

1. 函数定义：combinationSum 是一个接受两个参数的函数，candidates 是可选的数字数组，target 是我们想要达到的目标和。
2. 初始化结果和栈：
   • result 是一个数组，用于存储所有满足条件的组合。
   • stack 是一个栈，用于模拟递归过程。初始时，栈中包含一个对象，表示当前的组合为空（combination: []）、剩余目标值为 target（remaining: target），并且从候选数组的起始位置开始（start: 0）。
3. 主循环：当栈不为空时，进入循环，弹出栈顶元素，获取当前的组合、剩余目标值和起始索引。
4. 检查剩余目标值：如果剩余目标值为0，说明当前组合的数字之和等于目标值，将该组合添加到结果中，并继续进行下一轮循环。
5. 遍历候选数字：
   • 遍历候选数字，从当前的起始索引 start 开始。
   • 如果当前候选数字大于剩余目标值，则跳过该数字。
   • 否则，将当前候选数字添加到组合中，并更新剩余目标值（remaining - candidates[i]），同时将起始索引保持为 i，以允许重复使用当前候选数字。将这个新状态压入栈中。
6. 返回结果：当栈为空时，所有可能的组合都已被处理，函数返回结果数组 result