题目描述
给你一个 无重复元素 的整数数组 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
输出: []
题目分析
基本思想基于深度搜索和回溯。
首先对候选数组做一个排序,且由于数组都是正数,可以直接进行搜索。
代码
javascript">/*** @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 的输入:
javascript">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
数组是用来记录当前递归路径上选择的元素。
javascript">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
中的每个路径都是独立的,对它们的修改不会影响到其他路径。
举个例子:
假设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
的修改就不会影响已经保存的路径。