JavaScript 数组组合求和函数解析 - combinationSum() 函数详解
JavaScript 数组组合求和函数解析 - combinationSum() 函数详解
该函数 combinationSum(candidates, target) 的作用是找到所有由给定的 candidates 数组中的元素组成的和为 target 的组合。
function combinationSum(candidates, target) {
const result = [];
function backtrack(tempList, remain, start) {
if (remain < 0) {
return;
} else if (remain === 0) {
result.push([...tempList]);
} else {
for (let i = start; i < candidates.length; i++) {
tempList.push(candidates[i]);
backtrack(tempList, remain - candidates[i], i);
tempList.pop();
}
}
}
backtrack([], target, 0);
return result;
}
函数解析
-
函数定义: 函数
combinationSum接受两个参数:candidates: 一个包含候选数字的数组。target: 目标和。
-
结果数组: 函数定义了一个数组
result来存储所有找到的组合。 -
递归函数
backtrack: 该函数采用递归方式进行组合搜索,并接收三个参数:tempList: 当前找到的组合(数组)。remain: 还需要找到的和。start: 当前搜索candidates数组的起始位置。
-
递归逻辑:
remain < 0: 如果remain小于 0,说明当前组合不可能满足要求,直接返回。remain === 0: 如果remain等于 0,说明当前组合满足要求,将tempList添加到result数组中。remain > 0: 如果remain大于 0,需要继续搜索。- 循环遍历
candidates数组中从start位置开始的所有元素。 - 将当前元素添加到
tempList中。 - 递归调用
backtrack函数,继续搜索remain减去当前元素之后的组合,并将start位置设置为i(避免重复使用同一个元素)。 - 递归调用结束后,将当前元素从
tempList中弹出,继续搜索下一个元素。
- 循环遍历
-
初始调用: 函数最后调用
backtrack([], target, 0),开始递归搜索所有组合。 -
返回值: 函数返回包含所有满足要求的组合的数组
result。
运行逻辑示例
假设 candidates = [2, 3, 6, 7],target = 7。
- 初始调用
backtrack([], 7, 0),tempList = [],remain = 7。 - 循环遍历
candidates数组,从start = 0开始:i = 0,candidates[0] = 2,将 2 添加到tempList,tempList = [2],remain = 5,递归调用backtrack([2], 5, 0)。- ... (类似的递归过程,直到
remain等于 0 或小于 0)
- 递归结束后,
result数组将包含所有满足要求的组合。
总结
combinationSum 函数通过递归和回溯的方式,有效地找到了所有满足要求的数组组合。该函数利用了 backtrack 函数的递归特性,逐步尝试不同的元素组合,并通过 remain 和 tempList 记录当前状态,最终找到所有符合条件的组合。
原文地址: https://www.cveoy.top/t/topic/nat3 著作权归作者所有。请勿转载和采集!