LeetCode组合总和
题目描述
给你一个 无重复元素 的整数数组 candidates
和一个目标整数 target
,找出 candidates
中可以使数字和为目标数 target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target
的不同组合数少于 150
个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,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
输出: []
题目分析
基本思想基于深度搜索和回溯。
首先对候选数组做一个排序,且由于数组都是正数,可以直接进行搜索。
代码
/*** @param {number[]} candidates* @param {number} target* @return {number[][]}*/
var combinationSum = function (candidates, target) {candidates.sort((a, b) => a - b)var item = [],path = [];get_combin(candidates, target, 0, item, path);function get_combin(candidates, target, it, item, path) {if (target < 0)// 如果大于target 直接返回不继续搜索return;if (target == 0) {// 若得到路径,插入到item,不用清空path。因为需要继续搜索其余可能性path = path.slice() //进行复制,slice()没有参数就是复制item.push(path);return}for (var i = it; i < candidates.length; i++) {path.push(candidates[i]);get_combin(candidates, target - candidates[i], i, item, path)// 无论是该路径大于target还是等于target,都需要对其删除最后一个元素,进行其余支路的搜索path.pop()}}return item
};
代码分析
这段代码通过深度优先搜索(DFS
)和回溯算法来找出所有可能的组合,使得这些组合的元素之和等于目标值target
。下面是逐行解释:
-
candidates.sort((a, b) => a - b)
:
这行代码对输入数组candidates
进行排序。排序是为了使得我们能够按照从小到大的顺序进行搜索,这样可以更高效地找到可能的组合。 -
var item = [], path = [];
:
声明两个数组,item
用于存储所有找到的组合,path
用于存储当前搜索路径上的元素。 -
get_combin(candidates, target, 0, item, path);
:
调用递归函数get_combin
开始搜索。参数分别是候选数组、目标和、当前索引(从0开始)、存储所有组合的数组item
和当前路径的数组path
。 -
function get_combin(candidates, target, it, item, path) { ... }
:
定义递归函数get_combin
。 -
if (target < 0) return;
:
在递归函数中,如果当前目标和小于0,说明当前路径上的元素之和已经超过了目标值,因此不需要继续搜索这条路径。 -
if (target == 0) { ... }
:
在递归函数中,如果当前目标和等于0,说明找到了一个有效的组合。将当前路径path
复制并添加到item
数组中。 -
path = path.slice()
:
使用slice
方法复制当前路径,因为path
是引用类型,如果不复制,那么在递归调用中修改path
会影响到上一层递归的路径。 -
item.push(path);
:
将复制的路径添加到结果数组item
中。 -
return
:
找到有效组合后返回,不再继续搜索当前路径。 -
for (var i = it; i < candidates.length; i++) { ... }
:
使用for循环遍历候选数组,从当前索引it
开始,直到数组末尾。 -
path.push(candidates[i]);
:
将当前元素添加到路径中。 -
get_combin(candidates, target - candidates[i], i, item, path)
:
递归调用get_combin
函数,更新目标值为当前目标值减去当前元素的值,索引更新为当前索引i
(允许重复使用当前元素),继续搜索。 -
path.pop()
:
回溯步骤,从路径中移除最后一个元素,以便尝试其他可能的元素。
整个算法的关键在于递归和回溯。通过递归深入搜索每一种可能的组合,当找到一个有效组合或者超过目标值时回溯,尝试其他可能的组合。这种方法虽然简单,但效率较高,因为它避免了不必要的搜索。
案例分析
通过一个具体的例子来理解这段代码是如何工作的。我们使用示例 1 的输入:
candidates = [2,3,6,7], target = 7
-
排序:首先,
candidates
数组被排序为[2, 3, 6, 7]
。 -
初始化:
item
和path
被初始化为空数组。 -
开始递归:调用
get_combin(candidates, 7, 0, item, path)
。-
递归深度 1:
- 目标是 7,当前索引是 0,当前元素是 2。
- 因为 7 - 2 = 5,大于 0,所以继续递归。
path
变为[2]
。- 递归调用
get_combin([2,3,6,7], 5, 0, item, [2])
。
-
递归深度 2:
- 目标是 5,当前索引是 0,当前元素是 2。
- 因为 5 - 2 = 3,大于 0,所以继续递归。
path
变为[2, 2]
。- 递归调用
get_combin([2,3,6,7], 3, 0, item, [2, 2])
。
-
递归深度 3:
- 目标是 3,当前索引是 0,当前元素是 2。
- 因为 3 - 2 = 1,大于 0,所以继续递归。
path
变为[2, 2, 2]
。- 递归调用
get_combin([2,3,6,7], 1, 0, item, [2, 2, 2])
。
-
递归深度 4:
- 目标是 1,当前索引是 0,当前元素是 2。
- 因为 1 - 2 < 0,所以不继续递归。
- 回溯到递归深度 3。
-
递归深度 3 回溯:
- 从
path
中移除最后一个元素,path
变为[2, 2]
。 - 因为目标是 3,当前索引是 0,但我们已经尝试过当前元素,所以移动到下一个元素。
- 递归调用
get_combin([2,3,6,7], 3, 1, item, [2, 2])
。
- 从
-
递归深度 4:
- 目标是 3,当前索引是 1,当前元素是 3。
- 因为 3 - 3 = 0,等于 0,所以这是一个有效的组合。
path
变为[2, 2, 3]
。- 将
[2, 2, 3]
添加到item
中。
-
递归深度 3 回溯:
- 从
path
中移除最后一个元素,path
变为[2, 2]
。 - 移动到下一个元素,索引变为 1。
- 之后的
[2, 2, 6]
,[2, 2, 7]
都不行 - 此时,索引3已经遍历完毕,没有更多的元素可以添加到 path 中。
- 从
-
递归深度 2 回溯:
- 从
path
中移除最后一个元素,path
变为[2]
。 - 移动到下一个元素,索引变为 1。
- 从
-
递归深度 2:
- 目标是 5,当前索引是 1,当前元素是 3。
- 因为 5 - 3 = 2,大于 0,所以继续递归。
path
变为[2, 3]
。- 递归调用
get_combin([2,3,6,7], 2, 1, item, [2, 3])
。
-
递归深度 3:
- 目标是 2,当前索引是 1,当前元素是 3。
- 因为 2 - 3 < 0,所以不继续递归。
- 回溯到递归深度 2。
-
递归深度 2 回溯:
- 从
path
中移除最后一个元素,path
变为[2]
。 - 移动到下一个元素,索引变为 2。
- 从
-
递归深度 2:
- 目标是 5,当前索引是 2,当前元素是 6。
- 因为 5 - 6 < 0,所以不继续递归。
- 回溯到递归深度 1。
-
递归深度 1 回溯:
- 从
path
中移除最后一个元素,path
变为[]
。 - 移动到下一个元素,索引变为 1。
- 从
-
递归深度 1:
- 目标是 7,当前索引是 1,当前元素是 3。
- 因为 7 - 3 = 4,大于 0,所以继续递归。
path
变为[3]
。- 递归调用
get_combin([2,3,6,7], 4, 1, item, [3])
。
-
递归深度 2:
- 目标是 4,当前索引是 1,当前元素是 3。
- 因为 4 - 3 = 1,大于 0,所以继续递归。
path
变为[3, 3]
。- 递归调用
get_combin([2,3,6,7], 1, 1, item, [3, 3])
。
-
递归深度 3:
- 目标是 1,当前索引是 1,当前元素是 3。
- 因为 1 - 3 < 0,所以不继续递归。
- 回溯到递归深度 2。
-
递归深度 2 回溯:
- 从
path
中移除最后一个元素,path
变为[3]
。 - 移动到下一个元素,索引变为 2。
- 从
-
递归深度 2:
- 目标是 4,当前索引是 2,当前元素是 6。
- 因为 4 - 6 < 0,所以不继续递归。
- 回溯到递归深度 1。
-
递归深度 1 回溯:
- 从
path
中移除最后一个元素,path
变为[]
。 - 移动到下一个元素,索引变为 2。
- 从
-
递归深度 1:
- 目标是 7,当前索引是 2,当前元素是 6。
- 因为 7 - 6 = 1,大于 0,所以继续递归。
path
变为[6]
。- 递归调用
get_combin([2,3,6,7], 1, 2, item, [6])
。
-
递归深度 2:
- 目标是 1,当前索引是 2,当前元素是 6。
- 因为 1 - 6 < 0,所以不继续递归。
- 回溯到递归深度 1。
-
递归深度 1 回溯:
- 从
path
中移除最后一个元素,path
变为[]
。 - 移动到下一个元素,索引变为 3。
- 从
-
递归深度 1:
- 目标是 7,当前索引是 3,当前元素是 7。
- 因为 7 - 7 = 0,等于 0,所以这是一个有效的组合。
path
变为[7]
。- 将
[7]
添加到item
中。
-
-
返回结果:所有可能的组合已经被找到并添加到
item
中,函数返回item
。
最终,item
数组包含 [[2,2,3],[7]]
,这是所有可能的组合,它们的和等于目标值 7。
注意点
在JavaScript中,数组是通过引用传递的,这意味着当你将一个数组作为参数传递给函数时,函数内部对该数组的任何修改都会影响原始数组。在代码中,path
数组是用来记录当前递归路径上选择的元素。
if (target == 0) {path = path.slice()item.push(path);return
}
这里的关键是理解path
数组在递归调用中是如何被修改的:
-
递归调用中的修改:每次递归调用
get_combin
函数时,都会向path
中添加新的元素(path.push(candidates[i])
)。如果没有复制path
,那么当你在递归调用后返回上一层递归时,path
将保留着当前递归层的所有元素。 -
回溯:在每次递归调用后,你通过
path.pop()
移除最后一个元素,以便尝试其他可能的元素。但是,如果你没有在将path
添加到item
之前复制它,那么当你从path
中移除元素时,你实际上也在修改你刚刚添加到item
的路径。 -
复制的必要性:为了解决这个问题,你需要在将
path
添加到item
之前复制它。这样,你就可以在不影响原始path
的情况下,将当前路径的状态保存下来。path.slice()
创建了path
的一个浅拷贝,这意味着item
中的每个路径都是独立的,对它们的修改不会影响到其他路径。
举个例子:
假设candidates = [1, 2, 3]
,target = 4
。
- 递归深度 1:
path = []
,选择1,path = [1]
,target = 3
。 - 递归深度 2:
path = [1]
,选择2,path = [1, 2]
,target = 2
。 - 递归深度 3:
path = [1, 2]
,选择1,path = [1, 2, 1]
,target = 1
。
如果没有复制path
,当你在深度3的递归调用后返回到深度2时,path
将是[1, 2, 1]
,而不是[1, 2]
。这将导致你错误地尝试使用[1, 2, 1]
来找到剩余的target
值,而不是重新从[1, 2]
开始。
通过使用path.slice()
,你可以确保每次将path
添加到item
时,都是添加的一个独立副本,这样在后续的递归和回溯中对path
的修改就不会影响已经保存的路径。
相关文章:
LeetCode组合总和
题目描述 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被…...

MATLAB - 机械臂手眼标定(眼在手内) - 估计安装在机器人上的移动相机的姿态
系列文章目录 前言 本示例展示了如何为装有手眼构型摄像头的机械臂或机械手执行和验证手眼校准。 一、概述 执行手眼校准有助于操作配备末端执行器(简称 “手”)的机械臂,该末端执行器依赖于摄像头提供的视觉数据。一旦完成了眼在手外的校准&…...

【Unity】TextMeshPro 3.0.9无法显示emoji表情问题
需要下载TextMeshPro 3.2.x-pre.xxx版本,重新生成Sprite Asset文件解决 注意:若Package Manager没有搜到pre版本,那么可以去github下载到本地,再解压后,将文件夹移动到工程Packages文件夹下,然后打开Packa…...

金九银十软件测试面试题(800道)
今年你的目标是拿下大厂offer?还是多少万年薪?其实这些都离不开日积月累的过程。 为此我特意整理出一份(超详细笔记/面试题)它几乎涵盖了所有的测试开发技术栈,非常珍贵,人手一份 肝完进大厂 妥妥的&#…...

中国剩余定理 C++
题目 解题思路 原链接:https://www.acwing.com/solution/content/3539/ 大致步骤: 将第2,3,4…n个方程不断与第一个方程合并,得到方程a1k1a2k2m2-m1;用扩展欧几里得算法解出a1k1a2k2gcd(a1, a2)的结果,再将结果扩大(m2-m1)/d倍即…...

动态规划lc
先找到规律,然后找边界情况;部分特殊情况分类讨论 *递归 70.爬楼梯 简单 提示 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例 1: 输入:…...

介绍xshell的使用技巧
使用技巧目录 1. 开启左键选中即复制,右键点击即粘贴2. 开启撰写功能3. 开启日志记录功能 1. 开启左键选中即复制,右键点击即粘贴 参考:https://blog.csdn.net/chirrupy_hamal/article/details/108619262 2. 开启撰写功能 使用场景&#x…...

揭秘语音识别巨头1:国内外顶尖技术服务商全解析01(万字长文)
一、学习导航 解密语音识别巨头:国内顶尖技术服务商全解析00:学习地图 解密语音识别巨头:国内顶尖技术服务商全解析01:微软语音,商业No.1 解密语音识别巨头:国内顶尖技术服务商全解析02:百度…...
JAVA使用SM2算法生成密钥对加密解密加签验签
简介 SM2是非对称加密算法,一提非对称加密算法,第一想到的是RSA,没错,这个就是替代RSA的。它是基于椭圆曲线密码的公钥密码算法标准,其秘钥长度256bit,包含数字签名、密钥交换和公钥加密,用于替…...
uniapp(vue)打包web项目页面刷新后报404解决方案
一、问题概述 uniapp是一款优秀的跨平台开发框架,它可以帮助开发者快速构建出适用于多端的应用程序。然而,在项目打包后,有可能发现页面在刷新时会出现404错误。这无疑给用户体验带来了极大的困扰,下面我们就来分析一下这个问题。…...
ansible学习之ansible-vault
相关文档参考:http://www.ansible.com.cn/docs/playbooks_vault.html#what-can-be-encrypted-with-vault ansible-vault 功能介绍 Ansible-Vault是一个用于加密和管理Ansible playbook中敏感数据的工具。通过创建、编辑、加密、解密、查看和重置密码,可以安全地存储…...

封装el-upload组件,用于上传图片和视频的组件
使用环境 vue3element plus 需要根据后端返回结构修改的函数:onPreview onRemove onSuccess 组件使用 基本使用 源代码: <script setup> import AutoUploadFile from /components/auto-upload-file/index.vue function change(urls){console.log…...
6.将扩散模型与其他生成模型的关联(2)
1.归一化流与扩散模型 自一化流(Normalizing Flow)是生成模型,通过将易于处理的分布进行变换以队对高维数据进行建模。归一化流可以将简单的概率分布转化为极其复杂的分布,并用于强化学习、变分推理等领域。 现有的归一化流是基于变量替换公式构…...

【C++】基于红黑树封装set和map
🚀个人主页:小羊 🚀所属专栏:C 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 前言一、更高维度的泛型二、模版参数三、比较逻辑的重写四、迭代器4.1 const迭代器4.2 重载4.3 - -重载 五、完整代…...

24最新新手入门指南:Stable Diffusion!
前言 Stable Diffusion,一款新兴的开源AI绘画软件,正逐渐成为数字艺术家和爱好者的新宠。它的强大功能让用户能够轻松创造出令人印象深刻的数字艺术作品。 无论你是专业艺术家还是艺术新手,Stable Diffusion都为你提供了一个探索创造力的新…...

Java-基础
1. 导入模块不能纯粹的复制粘贴,要从new里导入,因为前者建立不了关联 2. 数组 String[] name{"张三","李四","王五"};int[] numsnew int[]{1,2,3};//二维String[][] names{{"张三","李四"},{"…...

二、后台管理系统布局菜单可拖动
前两天产品提出了一个需求,说后台管理系统的左边菜单的名称字数过多,遮挡了。希望能让客户能够看到全部的名称,给左侧菜单增加一个可拖动的功能,经过我的研究,这个功能最终也做出来了,先看效果,双击查看。 下面咱们进入实现步骤 第一步,找到文件。一般的项目中都存在l…...
socket和http区别
socket和http区别:1、主体不同;2、所处层次不同;3、连接状态不同;4、传输数据量不同;5、数据安全性不同;6、连接方式不同。其中,主体不同指的是socke是一个调用接口(API)…...

算法:974.和可以被K整除的子数组
题目 链接:leetcode链接 思路分析(前缀和 同余定理) 首先,我们要了解一下什么是同余定理 同余定理: 如果(a - b)/ p k …… 0 则 a % p b % p 证明我写在草稿纸上,如下图: 初…...

QD1-P8 HTML 格式化标签(font、pre、b、strong、i、u、del、s、sub、sup)
本节学习:HTML 格式化标签。 本节视频 www.bilibili.com/video/BV1n64y1U7oj?p8 一、font 标签 用途:定义文本的字体大小、颜色和 face(字体类型)。 示例 <!DOCTYPE html> <html><head><meta cha…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...