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

云建站公司做meta分析需注册的网站

news 2025/11/3 20:59:09

云建站公司,做meta分析需注册的网站,软件开发岗位要求,什么网站做兼职最好题目描述给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的同一个数字可以无限制重复被…

题目描述

给你一个 无重复元素 的整数数组 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中的每个路径都是独立的，对它们的修改不会影响到其他路径。