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

函数解析

  1. 结果数组 result: 用于存储所有符合条件的组合。

  2. 回溯函数 backtrack:

    • tempList: 临时数组,用于存储当前的组合。
    • remain: 当前还需要达到的目标值。
    • start: 从哪个位置开始搜索 candidates 数组。
  3. 递归调用核心逻辑:

    • if (remain < 0): 当前组合不符合条件,直接返回。
    • if (remain === 0): 当前组合符合条件,将其添加到 result 数组中。
    • else: 继续搜索 candidates 数组:
      • 使用 for 循环遍历 candidates 数组,从 start 位置开始。
      • 将当前数字 candidates[i] 添加到 tempList 中。
      • 递归调用 backtrack 函数,将 remain 减去当前数字,并继续从 i 位置开始搜索。
      • 递归调用结束后,从 tempList 中弹出最后一个数字,回到上一层递归。
  4. 初始调用: 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 函数来探索所有可能的组合。

JavaScript 中组合总和问题 (Combination Sum) 的回溯算法解析

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

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