JavaScript 中组合总和问题 (Combination Sum) 的回溯算法解析
JavaScript 中组合总和问题 (Combination Sum) 的回溯算法解析
这个函数用于在给定的 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;
}
函数解析
-
结果数组
result: 用于存储所有符合条件的组合。 -
回溯函数
backtrack:tempList: 临时数组,用于存储当前的组合。remain: 当前还需要达到的目标值。start: 从哪个位置开始搜索candidates数组。
-
递归调用核心逻辑:
if (remain < 0): 当前组合不符合条件,直接返回。if (remain === 0): 当前组合符合条件,将其添加到result数组中。else: 继续搜索candidates数组:- 使用
for循环遍历candidates数组,从start位置开始。 - 将当前数字
candidates[i]添加到tempList中。 - 递归调用
backtrack函数,将remain减去当前数字,并继续从i位置开始搜索。 - 递归调用结束后,从
tempList中弹出最后一个数字,回到上一层递归。
- 使用
-
初始调用:
backtrack([], target, 0)开始搜索所有符合条件的组合。
示例说明
假设 candidates = [2, 3, 6, 7] 且 target = 7。
- 初始调用:
backtrack([], 7, 0) - 第一次循环:
i = 0,tempList = [2],remain = 5,递归调用backtrack([2], 5, 0)。 - 第二次循环:
i = 0,tempList = [2, 2],remain = 3,递归调用backtrack([2, 2], 3, 0)。 - 第三次循环:
i = 0,tempList = [2, 2, 2],remain = 1,递归调用backtrack([2, 2, 2], 1, 0)。 - 第四次循环:
i = 0,tempList = [2, 2, 2, 2],remain = -1,不符合条件,返回。 - 第三次循环回溯: 从
tempList弹出2,tempList = [2, 2],remain = 3。 - 第三次循环继续:
i = 1,tempList = [2, 2, 3],remain = 0,符合条件,将[2, 2, 3]添加到result中。 - 第三次循环回溯: 从
tempList弹出3,tempList = [2, 2],remain = 3。 - ... 以此类推,直到所有符合条件的组合都找到。
总结
该函数通过递归和回溯的方式,遍历 candidates 数组的所有可能组合,并找到总和等于 target 的组合。它利用 tempList 和 remain 变量来跟踪当前的组合和剩余目标值,并使用递归调用 backtrack 函数来探索所有可能的组合。
原文地址: https://www.cveoy.top/t/topic/nauh 著作权归作者所有。请勿转载和采集!