当前位置：首页 > article >正文

LeetCode组合总和

article 2024/10/10 10:28:16

题目描述

给你一个 无重复元素 的整数数组 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。下面是逐行解释：

candidates.sort((a, b) => a - b)：
这行代码对输入数组candidates进行排序。排序是为了使得我们能够按照从小到大的顺序进行搜索，这样可以更高效地找到可能的组合。
var item = [], path = [];：
声明两个数组，item用于存储所有找到的组合，path用于存储当前搜索路径上的元素。
get_combin(candidates, target, 0, item, path);：
调用递归函数get_combin开始搜索。参数分别是候选数组、目标和、当前索引（从0开始）、存储所有组合的数组item和当前路径的数组path。
function get_combin(candidates, target, it, item, path) { ... }：
定义递归函数get_combin。
if (target < 0) return;：
在递归函数中，如果当前目标和小于0，说明当前路径上的元素之和已经超过了目标值，因此不需要继续搜索这条路径。
if (target == 0) { ... }：
在递归函数中，如果当前目标和等于0，说明找到了一个有效的组合。将当前路径path复制并添加到item数组中。
path = path.slice()：
使用slice方法复制当前路径，因为path是引用类型，如果不复制，那么在递归调用中修改path会影响到上一层递归的路径。
item.push(path);：
将复制的路径添加到结果数组item中。
return：
找到有效组合后返回，不再继续搜索当前路径。
for (var i = it; i < candidates.length; i++) { ... }：
使用for循环遍历候选数组，从当前索引it开始，直到数组末尾。
path.push(candidates[i]);：
将当前元素添加到路径中。
get_combin(candidates, target - candidates[i], i, item, path)：
递归调用get_combin函数，更新目标值为当前目标值减去当前元素的值，索引更新为当前索引i（允许重复使用当前元素），继续搜索。
path.pop()：
回溯步骤，从路径中移除最后一个元素，以便尝试其他可能的元素。

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

案例分析

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

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

排序：首先，candidates 数组被排序为 [2, 3, 6, 7]。
初始化：item 和 path 被初始化为空数组。
开始递归：调用 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 中。
返回结果：所有可能的组合已经被找到并添加到 item 中，函数返回 item。

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

注意点

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

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

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

递归调用中的修改：每次递归调用get_combin函数时，都会向path中添加新的元素（path.push(candidates[i])）。如果没有复制path，那么当你在递归调用后返回上一层递归时，path将保留着当前递归层的所有元素。
回溯：在每次递归调用后，你通过path.pop()移除最后一个元素，以便尝试其他可能的元素。但是，如果你没有在将path添加到item之前复制它，那么当你从path中移除元素时，你实际上也在修改你刚刚添加到item的路径。
复制的必要性：为了解决这个问题，你需要在将path添加到item之前复制它。这样，你就可以在不影响原始path的情况下，将当前路径的状态保存下来。path.slice()创建了path的一个浅拷贝，这意味着item中的每个路径都是独立的，对它们的修改不会影响到其他路径。