使用 JavaScript 解答 LeetCode 第 39 题,组合总和,中等难度。
题目
原题链接
本题目是 LeetCode 题库第 39 题,由此访问。
题目描述
给定一个无重复元素的数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的数字可以无限制重复被选取。
说明:
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解题
AC 样例
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
// 边界条件处理
if(candidates.length == 0) return [[]];
const res = [];
helper(candidates, target, 0, res, []);
return res;
};
/**
* @param ca: candidates
* @param t: target
* @param ci: current index
* @param res: result array
* @param cu: current item
* @return {}
*/
const helper = (ca, t, ci, res, cu) => {
// 回溯条件
if(t < 0) return;
// 终止递归条件
if(t == 0) {
// 数据复制,返回
res.push(Array.from(cu));
return ;
}
for (let i = ci; i < ca.length; i++) {
// 数据入栈
cu.push(ca[i]);
helper(ca, t-ca[i], i, res, cu);
// 数据出栈
cu.pop();
}
}
解题思路
本题采用回溯法,对题目边界条件进行处理后进行递归。每次取出一个数据入栈,进一步试探,如其与目标值差值小于零,则对数据进行出栈操作;如其与目标值差值等于零,则将数据作为答案一部分返回;如其与目标值差值大于零,则继续进一步试探。重复上述步骤,直至所有数据被试探完毕,即可得到最终答案。
语法点
在上述 AC 样例代码中,helper
函数对终止递归条件的处理中,有一语句是进行数据复制:
res.push(Array.from(cu));
如果未对数据进行复制,直接进行传递,即代码为:
res.push(cu);
由于变量 cu 不是基本类型数据(如字符串型、数字型、布尔型),这种情况下对数组 res 插入的值为变量 cu 的存储地址。在后续算法执行过程中,变量 cu 的值将会被多次覆盖,导致答案与实际计算结果不符。
JavaScript 数组原型提供了 Array.from()
方法,该方法从一个类数组或可迭代对象中创建一个新的、浅复制的数组实例。关于浅复制相关的内容可参考文章 JavaScript:深复制与浅复制。
将复制得到的实例参与计算,原数据在后续计算中值发生变化时,不对复制实例产生影响。确保当前步骤中得到的数据不被修改,得到完整记录。