LeetCode组合总和

题目描述

给你一个 无重复元素 的整数数组 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
输出: []

题目分析

基本思想基于深度搜索和回溯。

首先对候选数组做一个排序，且由于数组都是正数，可以直接进行搜索。

代码

/*** @param {number[]} candidates* @param {number} target* @return {number[][]}*/
var combinationSum = function (candidates, target) {candidates.sort((a, b) => a - b)var item = [],path = [];get_combin(candidates, target, 0, item, path);function get_combin(candidates, target, it, item, path) {if (target < 0)// 如果大于target 直接返回不继续搜索return;if (target == 0) {// 若得到路径，插入到item，不用清空path。因为需要继续搜索其余可能性path = path.slice()  //进行复制，slice()没有参数就是复制item.push(path);return}for (var i = it; i < candidates.length; i++) {path.push(candidates[i]);get_combin(candidates, target - candidates[i], i, item, path)// 无论是该路径大于target还是等于target，都需要对其删除最后一个元素，进行其余支路的搜索path.pop()}}return item
};

代码分析

这段代码通过深度优先搜索（DFS）和回溯算法来找出所有可能的组合，使得这些组合的元素之和等于目标值target。下面是逐行解释：

1. candidates.sort((a, b) => a - b)：
   这行代码对输入数组candidates进行排序。排序是为了使得我们能够按照从小到大的顺序进行搜索，这样可以更高效地找到可能的组合。

2. var item = [], path = [];：
   声明两个数组，item用于存储所有找到的组合，path用于存储当前搜索路径上的元素。

3. get_combin(candidates, target, 0, item, path);：
   调用递归函数get_combin开始搜索。参数分别是候选数组、目标和、当前索引（从0开始）、存储所有组合的数组item和当前路径的数组path。

4. function get_combin(candidates, target, it, item, path) { ... }：
   定义递归函数get_combin。

5. if (target < 0) return;：
   在递归函数中，如果当前目标和小于0，说明当前路径上的元素之和已经超过了目标值，因此不需要继续搜索这条路径。

6. if (target == 0) { ... }：
   在递归函数中，如果当前目标和等于0，说明找到了一个有效的组合。将当前路径path复制并添加到item数组中。

7. path = path.slice()：
   使用slice方法复制当前路径，因为path是引用类型，如果不复制，那么在递归调用中修改path会影响到上一层递归的路径。

8. item.push(path);：
   将复制的路径添加到结果数组item中。

9. return：
   找到有效组合后返回，不再继续搜索当前路径。

10. for (var i = it; i < candidates.length; i++) { ... }：
    使用for循环遍历候选数组，从当前索引it开始，直到数组末尾。

11. path.push(candidates[i]);：
    将当前元素添加到路径中。

12. get_combin(candidates, target - candidates[i], i, item, path)：
    递归调用get_combin函数，更新目标值为当前目标值减去当前元素的值，索引更新为当前索引i（允许重复使用当前元素），继续搜索。

13. path.pop()：
    回溯步骤，从路径中移除最后一个元素，以便尝试其他可能的元素。

整个算法的关键在于递归和回溯。通过递归深入搜索每一种可能的组合，当找到一个有效组合或者超过目标值时回溯，尝试其他可能的组合。这种方法虽然简单，但效率较高，因为它避免了不必要的搜索。

案例分析

通过一个具体的例子来理解这段代码是如何工作的。我们使用示例 1 的输入：

candidates = [2,3,6,7], target = 7

1. 排序：首先，candidates 数组被排序为 [2, 3, 6, 7]。

2. 初始化：item 和 path 被初始化为空数组。

3. 开始递归：调用 get_combin(candidates, 7, 0, item, path)。

   • 递归深度 1：

     • 目标是 7，当前索引是 0，当前元素是 2。
     • 因为 7 - 2 = 5，大于 0，所以继续递归。
     • path 变为 [2]。
     • 递归调用 get_combin([2,3,6,7], 5, 0, item, [2])。

   • 递归深度 2：

     • 目标是 5，当前索引是 0，当前元素是 2。
     • 因为 5 - 2 = 3，大于 0，所以继续递归。
     • path 变为 [2, 2]。
     • 递归调用 get_combin([2,3,6,7], 3, 0, item, [2, 2])。

   • 递归深度 3：

     • 目标是 3，当前索引是 0，当前元素是 2。
     • 因为 3 - 2 = 1，大于 0，所以继续递归。
     • path 变为 [2, 2, 2]。
     • 递归调用 get_combin([2,3,6,7], 1, 0, item, [2, 2, 2])。

   • 递归深度 4：

     • 目标是 1，当前索引是 0，当前元素是 2。
     • 因为 1 - 2 < 0，所以不继续递归。
     • 回溯到递归深度 3。

   • 递归深度 3 回溯：

     • 从 path 中移除最后一个元素，path 变为 [2, 2]。
     • 因为目标是 3，当前索引是 0，但我们已经尝试过当前元素，所以移动到下一个元素。
     • 递归调用 get_combin([2,3,6,7], 3, 1, item, [2, 2])。

   • 递归深度 4：

     • 目标是 3，当前索引是 1，当前元素是 3。
     • 因为 3 - 3 = 0，等于 0，所以这是一个有效的组合。
     • path 变为 [2, 2, 3]。
     • 将 [2, 2, 3] 添加到 item 中。

   • 递归深度 3 回溯：

     • 从 path 中移除最后一个元素，path 变为 [2, 2]。
     • 移动到下一个元素，索引变为 1。
     • 之后的[2, 2, 6]，[2, 2, 7]都不行
     • 此时，索引3已经遍历完毕，没有更多的元素可以添加到 path 中。

   • 递归深度 2 回溯：

     • 从 path 中移除最后一个元素，path 变为 [2]。
     • 移动到下一个元素，索引变为 1。

   • 递归深度 2：

     • 目标是 5，当前索引是 1，当前元素是 3。
     • 因为 5 - 3 = 2，大于 0，所以继续递归。
     • path 变为 [2, 3]。
     • 递归调用 get_combin([2,3,6,7], 2, 1, item, [2, 3])。

   • 递归深度 3：

     • 目标是 2，当前索引是 1，当前元素是 3。
     • 因为 2 - 3 < 0，所以不继续递归。
     • 回溯到递归深度 2。

   • 递归深度 2 回溯：

     • 从 path 中移除最后一个元素，path 变为 [2]。
     • 移动到下一个元素，索引变为 2。

   • 递归深度 2：

     • 目标是 5，当前索引是 2，当前元素是 6。
     • 因为 5 - 6 < 0，所以不继续递归。
     • 回溯到递归深度 1。

   • 递归深度 1 回溯：

     • 从 path 中移除最后一个元素，path 变为 []。
     • 移动到下一个元素，索引变为 1。

   • 递归深度 1：

     • 目标是 7，当前索引是 1，当前元素是 3。
     • 因为 7 - 3 = 4，大于 0，所以继续递归。
     • path 变为 [3]。
     • 递归调用 get_combin([2,3,6,7], 4, 1, item, [3])。

   • 递归深度 2：

     • 目标是 4，当前索引是 1，当前元素是 3。
     • 因为 4 - 3 = 1，大于 0，所以继续递归。
     • path 变为 [3, 3]。
     • 递归调用 get_combin([2,3,6,7], 1, 1, item, [3, 3])。

   • 递归深度 3：

     • 目标是 1，当前索引是 1，当前元素是 3。
     • 因为 1 - 3 < 0，所以不继续递归。
     • 回溯到递归深度 2。

   • 递归深度 2 回溯：

     • 从 path 中移除最后一个元素，path 变为 [3]。
     • 移动到下一个元素，索引变为 2。

   • 递归深度 2：

     • 目标是 4，当前索引是 2，当前元素是 6。
     • 因为 4 - 6 < 0，所以不继续递归。
     • 回溯到递归深度 1。

   • 递归深度 1 回溯：

     • 从 path 中移除最后一个元素，path 变为 []。
     • 移动到下一个元素，索引变为 2。

   • 递归深度 1：

     • 目标是 7，当前索引是 2，当前元素是 6。
     • 因为 7 - 6 = 1，大于 0，所以继续递归。
     • path 变为 [6]。
     • 递归调用 get_combin([2,3,6,7], 1, 2, item, [6])。

   • 递归深度 2：

     • 目标是 1，当前索引是 2，当前元素是 6。
     • 因为 1 - 6 < 0，所以不继续递归。
     • 回溯到递归深度 1。

   • 递归深度 1 回溯：

     • 从 path 中移除最后一个元素，path 变为 []。
     • 移动到下一个元素，索引变为 3。

   • 递归深度 1：

     • 目标是 7，当前索引是 3，当前元素是 7。
     • 因为 7 - 7 = 0，等于 0，所以这是一个有效的组合。
     • path 变为 [7]。
     • 将 [7] 添加到 item 中。

4. 返回结果：所有可能的组合已经被找到并添加到 item 中，函数返回 item。

最终，item 数组包含 [[2,2,3],[7]]，这是所有可能的组合，它们的和等于目标值 7。

注意点

在JavaScript中，数组是通过引用传递的，这意味着当你将一个数组作为参数传递给函数时，函数内部对该数组的任何修改都会影响原始数组。在代码中，path数组是用来记录当前递归路径上选择的元素。

if (target == 0) {path = path.slice()item.push(path);return
}

这里的关键是理解path数组在递归调用中是如何被修改的：

1. 递归调用中的修改：每次递归调用get_combin函数时，都会向path中添加新的元素（path.push(candidates[i])）。如果没有复制path，那么当你在递归调用后返回上一层递归时，path将保留着当前递归层的所有元素。

2. 回溯：在每次递归调用后，你通过path.pop()移除最后一个元素，以便尝试其他可能的元素。但是，如果你没有在将path添加到item之前复制它，那么当你从path中移除元素时，你实际上也在修改你刚刚添加到item的路径。

3. 复制的必要性：为了解决这个问题，你需要在将path添加到item之前复制它。这样，你就可以在不影响原始path的情况下，将当前路径的状态保存下来。path.slice()创建了path的一个浅拷贝，这意味着item中的每个路径都是独立的，对它们的修改不会影响到其他路径。

举个例子：

假设candidates = [1, 2, 3]，target = 4。

• 递归深度 1：path = []，选择1，path = [1]，target = 3。
• 递归深度 2：path = [1]，选择2，path = [1, 2]，target = 2。
• 递归深度 3：path = [1, 2]，选择1，path = [1, 2, 1]，target = 1。

如果没有复制path，当你在深度3的递归调用后返回到深度2时，path将是[1, 2, 1]，而不是[1, 2]。这将导致你错误地尝试使用[1, 2, 1]来找到剩余的target值，而不是重新从[1, 2]开始。

通过使用path.slice()，你可以确保每次将path添加到item时，都是添加的一个独立副本，这样在后续的递归和回溯中对path的修改就不会影响已经保存的路径。