学习记录:js算法(八十二):组合总和

ops/2024/11/2 23:41:37/

文章目录

    • 组合总和
      • 思路一
      • 思路二
      • 思路三

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
23 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3:
输入: candidates = [2], target = 1
输出: []

思路一

function combinationSum(candidates, target) {const res = [];const backtrack = (path, sum, startIndex) => {if (sum === target) {res.push([...path]);return;}if (sum > target) {return;}for (let i = startIndex; i < candidates.length; i++) {path.push(candidates[i]);sum += candidates[i];backtrack(path, sum, i); // 注意这里是i,允许重复选取同一个元素path.pop();sum -= candidates[i];}};backtrack([], 0, 0);return res;
}

讲解
这道题目可以通过使用回溯算法(Backtracking)来解决。回溯算法是一种通过试探搜索(试错法)来寻找所有可能的解决方案的算法

  1. 初始化:创建一个空的路径数组path来存储当前的组合,以及一个空的结果数组res来存储所有有效的组合。
  2. 递归函数:定义一个递归函数backtrack,它接受以下参数:
    ○ 当前路径path,
    ○ 当前路径的和sum,
    ○ 下一个开始搜索的索引startIndex。
  3. 基本结束条件:如果当前路径的和sum等于target,将当前路径path拷贝一份加入结果数组res,然后返回。
  4. 剪枝条件:如果当前路径的和sum大于target,直接返回,不再继续探索。
  5. 回溯过程:对于startIndex到数组末尾的每一个数字,执行以下操作:
    ○ 将当前数字添加到路径path中,并更新路径的和sum。
    ○ 递归调用backtrack函数,传递更新后的path、sum和下一个开始搜索的索引。
    ○ 回溯,即将当前数字从路径path中移除,并恢复路径的和sum。
  6. 开始回溯:调用backtrack函数,传入初始的path、sum和startIndex。
  7. 返回结果:最后返回结果数组res。

思路二

var combinationSum = function (candidates, target) {const dp = Array.from({ length: target + 1 }, () => []);dp[0] = [[]]; // 目标为0时,只有一种组合:空数组for (const num of candidates) {for (let i = num; i <= target; i++) {for (const combination of dp[i - num]) {dp[i].push([...combination, num]); // 添加当前数字}}}return dp[target];
};

讲解

  1. 定义函数:combinationSum 是一个接受两个参数的函数,candidates 是可选的数字数组,target 是我们想要达到的目标和。
  2. 创建动态规划数组:dp 是一个二维数组,其中 dp[i] 存储所有和为 i 的组合。我们初始化一个长度为 target + 1 的数组,每个元素都是一个空数组。
  3. 初始化基例:dp[0] 被初始化为包含一个空数组的数组,表示和为 0 的组合是唯一的,即不选任何数字。
  4. 循环:
    • 外层循环:遍历每个候选数字 num。
    • 中层循环:从 num 开始,遍历到 target。这是因为我们只需考虑从 num 开始的目标值,因为小于 num 的目标值无法包含 num。
    • 内层循环:遍历 dp[i - num] 中的每个组合。dp[i - num] 表示在目标值为 i - num 时的所有组合。
      • 组合构建:对于每个组合,我们创建一个新的组合,将当前数字 num 添加到其中,并将其推入 dp[i] 中。
  5. 返回结果:最后,函数返回 dp[target],即所有和为 target 的组合。

思路三

var combinationSum = function (candidates, target) {const result = [];const stack = [{ combination: [], remaining: target, start: 0 }];while (stack.length) {const { combination, remaining, start } = stack.pop();if (remaining === 0) {result.push(combination);continue;}for (let i = start; i < candidates.length; i++) {if (remaining < candidates[i]) continue;stack.push({ combination: [...combination, candidates[i]], remaining: remaining - candidates[i], start: i });}}return result;
};

讲解

  1. 函数定义:combinationSum 是一个接受两个参数的函数,candidates 是可选的数字数组,target 是我们想要达到的目标和。
  2. 初始化结果和栈:
    • result 是一个数组,用于存储所有满足条件的组合。
    • stack 是一个栈,用于模拟递归过程。初始时,栈中包含一个对象,表示当前的组合为空(combination: [])、剩余目标值为 target(remaining: target),并且从候选数组的起始位置开始(start: 0)。
  3. 主循环:当栈不为空时,进入循环,弹出栈顶元素,获取当前的组合、剩余目标值和起始索引。
  4. 检查剩余目标值:如果剩余目标值为0,说明当前组合的数字之和等于目标值,将该组合添加到结果中,并继续进行下一轮循环。
  5. 遍历候选数字:
    • 遍历候选数字,从当前的起始索引 start 开始。
    • 如果当前候选数字大于剩余目标值,则跳过该数字。
    • 否则,将当前候选数字添加到组合中,并更新剩余目标值(remaining - candidates[i]),同时将起始索引保持为 i,以允许重复使用当前候选数字。将这个新状态压入栈中。
  6. 返回结果:当栈为空时,所有可能的组合都已被处理,函数返回结果数组 result

http://www.ppmy.cn/ops/130549.html

相关文章

Docker:容器化和虚拟化

虚拟化 虚拟化是一种资源管理技术&#xff0c;它将计算机的各种实体资源&#xff08;如CPU、内存、磁盘空间、网络适配器等&#xff09;予以抽象、转换后呈现出来&#xff0c;并可供分割、组合为一个或多个电脑配置环境。这些资源的新虚拟部分是不受现有资源的架设方式、地域或…

git常见指令

概念 远程仓库和本地仓库 常用指令&#xff1a; ls/ll查看当前目录cat查看文件内容touch创建文件vivi编辑器 备注&#xff1a; git GUI&#xff1a;是git提供的图形化工具 GIT Bash&#xff1a;Git提供的命令行工具 在安装GIT后要配置用户和账号&#xff01; 配置用户信息 …

HTTP服务器测试与优化

目录 1 搭建一个基础的HTTP服务器 2 长连接测试 3 测试错误报文的处理 4 测试业务处理耗时超过超时时间的处理 5 测试同时收到多条正常请求 6 大文件传输测试 7 压力测试 1 搭建一个基础的HTTP服务器 在这个部分&#xff0c;我们需要搭建一个最简单的HTTP服务器&#xf…

Java的包、final关键字以及代码块

Java的包、final关键字以及代码块 一、包 包的作用 &#xff1a; ​ 包就是文件夹&#xff0c;用来管理各种不同功能的Java类 包名的书写规则&#xff1a; ​ 公司域名反写 包的作用&#xff0c;需要全部英文小写&#xff0c;见名知意 什么是全类名&#xff1a; ​ 包名…

固定电话怎么认证显示公司名称?

在当今商业环境中&#xff0c;企业的联系方式&#xff0c;尤其是固定电话&#xff0c;不仅是与客户沟通的重要桥梁&#xff0c;也是展示企业专业形象的一部分。许多企业希望通过拨打固定电话联系客户时&#xff0c;能够对外显示公司名称&#xff0c;以此来增加电话的可信度和品…

大数据之文件服务器方案

大数据文件服务器方案 一&#xff0c;文件服务器常用框架 二&#xff0c;文件服务器常用框架的实现技术 文件服务器常用框架 文件服务器是一种专门用于存储、管理和共享文件的服务器&#xff0c;其常用框架的实现技术涉及多个方面&#xff0c;以下是一些主要的实现技术及其详…

CSS3新增盒子属性(三)

1、CSS3新增盒子属性 1.1 box-sizing 设置盒子的大小。 content-box&#xff1a;设置内容区的大小&#xff1b;border-box&#xff1a;设置盒子的总大小。 <!DOCTYPE html> <html lang"zh-CN"><head><meta charset"UTF-8"><t…

el-select、el-autocomplete的选项内容过长显示完整内容

问题&#xff1a; el-select、el-autocomplete的选项内容过长需要看清完整内容 解决方案&#xff1a; 使用el-popover悬停显示完整内容 代码&#xff1a; <el-form-item label"备注" prop"remark"><el-autocomplete v-model"form.remar…