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。

函数解析

  1. 初始化结果数组: 函数首先定义了一个名为 result 的数组,用于存储所有符合条件的数字组合。

  2. 回溯函数 backtrack: 该函数使用递归来遍历 candidates 数组,并寻找所有可能的组合。

    • tempList: 一个临时数组,用于存储当前的数字组合。
    • remain: 一个整数,代表剩余需要达成的目标值。
    • start: 一个整数,代表遍历 candidates 数组的起始位置。
  3. 递归逻辑:

    • 基线条件:
      • 如果 remain < 0,说明当前的数字组合已经超过了 target,返回。
      • 如果 remain === 0,说明当前的数字组合满足条件,将 tempList 复制到 result 数组中。
    • 递归遍历:
      • 从 start 位置开始,依次遍历 candidates 数组中的数字。
      • 将当前数字 candidates[i] 添加到 tempList 中,并递归调用 backtrack 函数,更新 remain 和 start 位置。
      • 从 tempList 中移除当前数字 candidates[i],回溯到上一层递归。
  4. 调用 backtrack 函数: 最后,调用 backtrack 函数,传入空数组 []、目标值 target 和起始位置 0,返回 result 数组。

示例

假设 candidates = [2, 3, 5] 且 target = 8,则 combinationSum 函数会返回以下结果:

[ [ 2, 2, 2, 2 ], [ 2, 3, 3 ], [ 3, 5 ] ]

总结

combinationSum 函数使用回溯算法,通过递归遍历 candidates 数组,寻找所有满足条件的数字组合,使其总和等于给定的 target 值。该函数在组合问题中具有广泛的应用,可以用于解决各种需要寻找所有可能组合的问题。

JavaScript 回溯算法实现组合总和:combinationSum 函数解析

原文地址: https://www.cveoy.top/t/topic/natX 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录