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;
}

函数解析

  1. 函数定义: 函数 combinationSum 接受两个参数:

    • candidates: 一个包含候选数字的数组。
    • target: 目标和。
  2. 结果数组: 函数定义了一个数组 result 来存储所有找到的组合。

  3. 递归函数 backtrack: 该函数采用递归方式进行组合搜索,并接收三个参数:

    • tempList: 当前找到的组合(数组)。
    • remain: 还需要找到的和。
    • start: 当前搜索 candidates 数组的起始位置。
  4. 递归逻辑:

    • remain < 0: 如果 remain 小于 0,说明当前组合不可能满足要求,直接返回。
    • remain === 0: 如果 remain 等于 0,说明当前组合满足要求,将 tempList 添加到 result 数组中。
    • remain > 0: 如果 remain 大于 0,需要继续搜索。
      • 循环遍历 candidates 数组中从 start 位置开始的所有元素。
      • 将当前元素添加到 tempList 中。
      • 递归调用 backtrack 函数,继续搜索 remain 减去当前元素之后的组合,并将 start 位置设置为 i(避免重复使用同一个元素)。
      • 递归调用结束后,将当前元素从 tempList 中弹出,继续搜索下一个元素。
  5. 初始调用: 函数最后调用 backtrack([], target, 0),开始递归搜索所有组合。

  6. 返回值: 函数返回包含所有满足要求的组合的数组 result。

运行逻辑示例

假设 candidates = [2, 3, 6, 7],target = 7。

  1. 初始调用 backtrack([], 7, 0),tempList = [], remain = 7。
  2. 循环遍历 candidates 数组,从 start = 0 开始:
    • i = 0, candidates[0] = 2,将 2 添加到 tempList,tempList = [2],remain = 5,递归调用 backtrack([2], 5, 0)。
    • ... (类似的递归过程,直到 remain 等于 0 或小于 0)
  3. 递归结束后,result 数组将包含所有满足要求的组合。

总结

combinationSum 函数通过递归和回溯的方式,有效地找到了所有满足要求的数组组合。该函数利用了 backtrack 函数的递归特性,逐步尝试不同的元素组合,并通过 remain 和 tempList 记录当前状态,最终找到所有符合条件的组合。

JavaScript 数组组合求和函数解析 - combinationSum() 函数详解

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

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