JavaScript 回溯算法实现组合总和:combinationSum 函数解析
JavaScript 回溯算法实现组合总和:combinationSum 函数解析
本文将深入解析 JavaScript 中的 combinationSum 函数,该函数利用回溯算法 (Backtracking) 找出所有满足条件的数字组合,使其总和等于给定的目标值。
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;
}
函数参数
candidates: 一个包含数字的数组,代表所有可选择的数字。target: 一个整数,代表目标值。
函数返回值
- 一个二维数组,其中每个子数组都是一组满足条件的数字组合,它们的总和等于
target。
函数解析
-
初始化结果数组: 函数首先定义了一个名为
result的数组,用于存储所有符合条件的数字组合。 -
回溯函数
backtrack: 该函数使用递归来遍历candidates数组,并寻找所有可能的组合。tempList: 一个临时数组,用于存储当前的数字组合。remain: 一个整数,代表剩余需要达成的目标值。start: 一个整数,代表遍历candidates数组的起始位置。
-
递归逻辑:
- 基线条件:
- 如果
remain < 0,说明当前的数字组合已经超过了target,返回。 - 如果
remain === 0,说明当前的数字组合满足条件,将tempList复制到result数组中。
- 如果
- 递归遍历:
- 从
start位置开始,依次遍历candidates数组中的数字。 - 将当前数字
candidates[i]添加到tempList中,并递归调用backtrack函数,更新remain和start位置。 - 从
tempList中移除当前数字candidates[i],回溯到上一层递归。
- 从
- 基线条件:
-
调用
backtrack函数: 最后,调用backtrack函数,传入空数组[]、目标值target和起始位置0,返回result数组。
示例
假设 candidates = [2, 3, 5] 且 target = 8,则 combinationSum 函数会返回以下结果:
[ [ 2, 2, 2, 2 ], [ 2, 3, 3 ], [ 3, 5 ] ]
总结
combinationSum 函数使用回溯算法,通过递归遍历 candidates 数组,寻找所有满足条件的数字组合,使其总和等于给定的 target 值。该函数在组合问题中具有广泛的应用,可以用于解决各种需要寻找所有可能组合的问题。
原文地址: https://www.cveoy.top/t/topic/natX 著作权归作者所有。请勿转载和采集!