【LeetCode】39.组合总和
组合总和
题目描述:
给你一个 无重复元素 的整数数组 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
输出: []
提示:
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
思路分析:
使用深度优先遍历 实现,使用一个列表,在 深度优先遍历 变化的过程中,遍历所有可能的列表并判断当前列表是否符合题目的要求。如果不符合进行剪枝。
说明:
- 以 target = 7 为 根结点 ,创建一个分支的时 做减法 ;
- 每一个箭头表示:从父亲结点的数值减去边上的数值,得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值;
- 减到 0或者负数的时候停止,即:结点 0和负数结点成为叶子结点;
- 同时每一次搜索的时候设置 下一轮搜索的起点
begin,即:从每一层的第 222 个结点开始,都不能再搜索产生同一层结点已经使用过的candidate里的元素。
代码实现注解:
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {//定义一个返回结果的集合List<List<Integer>> res = new ArrayList<>();//定义一个存储树路径上的节点值int len = candidates.length;if(len == 0)return res;//升序排序Arrays.sort(candidates);//定义一个表示数组的长度变量Deque<Integer> path = new ArrayDeque<>();//深度搜索,调用函数dfs(candidates, 0, len, target, path, res);return res;}private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path,List<List<Integer>> res) {// 由于进入更深层的时候,小于 0 的部分被剪枝,因此递归终止条件值只判断等于 0 的情况if (target == 0) {//将节点值存入返回集合res.add(new ArrayList<>(path));return;}//begin用于记录当前遍历位置for (int i = begin; i < len; i++) {//剪枝操作,将叶子节点小于0的分支减掉if (target - candidates[i] < 0) {break;}path.addLast(candidates[i]);//将i传入可有效避免结果重复dfs(candidates, i, len, target - candidates[i], path, res);//回溯,移除path中最后一个元素path.removeLast();}}
}

相关文章:
【LeetCode】39.组合总和
组合总和 题目描述: 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个…...
用JS来控制遥控车(一行代码即可连接, 超简单!)
简介 有些时候我们想要做车辆的某一个功能,但是又不想浪费时间做整辆小车时,一般会去买一辆差不多的遥控车来改,但是那也比较麻烦,市面上好像也没有便宜的直接提供编程接口的遥控车。所以就自己做一个吧~。 主要是要实现向外提供…...
MyBatis-Plus如何优雅的配置多租户及分页
MyBatis-Plus如何优雅的配置多租户及分页 一、配置多租户1、步骤一2、步骤二3、步骤三步骤四 二、配置分页1、步骤一2、步骤二3、步骤三 一、配置多租户 TenantLineInnerInterceptor 是 MyBatis-Plus 提供的一个插件,用于实现多租户的数据隔离。通过这个插件&#…...
国产操作系统上Vim的详解01--vim基础篇 _ 统信 _ 麒麟 _ 中科方德
原文链接:国产操作系统上Vim的详解01–vim基础篇 | 统信 | 麒麟 | 中科方德 Hello,大家好啊!今天给大家带来一篇在国产操作系统上使用Vim的详解文章。Vim是一款功能强大且高度可定制的文本编辑器,广泛应用于编程和日常文本编辑中。…...
如何正确理解事件溯源架构模式?
在微服务架构盛行的当下,DDD(领域驱动设计)也得到了崭新的发展。同时,随着DDD的不断发展,也诞生了一些新的设计思想和开发模式,今天要介绍的事件溯源是其中具有代表性的一种模式。 事件溯源模式是DDD领域中…...
【漏洞复现】电信网关配置管理系统 rewrite.php 文件上传漏洞
0x01 产品简介 中国电信集团有限公司(英文名称"China Telecom”、简称“"中国电信”)成立于2000年9月,是中国特大型国有通信企业、上海世博会全球合作伙伴。电信网关配置管理系统是一个用于管理和配置电信网络中网关设备的软件系统。它可以帮助网络管理员…...
线性调整率:LINE REGULATION详解
目录 一、概述 二、 举例 一、概述 LDO(低压差线性稳压器)的LINE REGULATION(线路调整或线性调整)参数是一个衡量稳压器输出稳定性的重要指标。它反映了LDO输出电压对输入电压变化的响应程度。 当输入电压在其规定的工作范围内变…...
Workfine默认首页功能详解
一、基本介绍 Workfine V6.3推出了默认的用户首页功能,这样用户在登入系统后就可以通过默认的首页栏进行一些业务操作。第一版的用户首页功能布局了审批,制单,业务导航,便捷入口,消息和预警六大块内容,后续…...
CSAPP Lab07——Malloc Lab完成思路
等不到天黑 烟火不会太完美 回忆烧成灰 还是等不到结尾 ——她说 完整代码见:CSAPP/malloclab-handout at main SnowLegend-star/CSAPP (github.com) Malloc Lab 按照惯例,我先是上来就把mm.c编译了一番,结果产生如下报错。搜索过后看样子应…...
简单、免费、无广告的高性能多线程文件下载工具
一、简介 1、它是一款免费、无广告的高性能多线程文件下载工具。它界面简洁,简单好用,压缩包大小仅有 0.7MB,目前仅支持 Windows 平台。 2、使用方法:点击程序左上角的【】按钮,将需要的链接输入进去后点击【下载】即…...
【退役之重学 SQL】什么是笛卡尔积
一、初识笛卡尔积 概念: 笛卡尔积是指在关系型数据库中,两个表进行 join 操作时,没有指定任何条件,导致生成的结果集,是两个表中所有行的组合。 简单来说: 笛卡尔积是两个表的乘积,结果集中的每…...
Vue3禁止 H5 界面放大与缩小功能
Vue3禁止 H5 界面放大与缩小功能 一、前言1.第一步2.第二部3.总结 一、前言 当涉及到禁止 H5 界面的放大与缩小功能时,Vue 3 提供了一种方便的方式来处理。我们可以使用 <script setup> 语法,将相关代码添加到 App.vue 组件中,以确保在…...
上位机图像处理和嵌入式模块部署(f407 mcu中tf卡读写和fatfs挂载)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 很早之前,个人对tf卡并不是很重视,觉得它就是一个存储工具而已。后来在移植v3s芯片的时候,才发现很多的soc其实…...
汽车识别项目
窗口设计 这里的代码放在py文件最前面或者最后面都无所谓 # 创建主窗口 window tk.Tk() window.title("图像目标检测系统") window.geometry(1000x650) # 设置窗口大小# 创建背景画布并使用grid布局管理器 canvas_background tk.Canvas(window, width1000, height…...
【面试题-012】什么是Spring 它有哪些优势
文章目录 Spring有哪些优势有哪些优势Spring和Springboot区别在 Spring 框架中,什么是AOP核心概念应用场景 Spring有哪些通知类型 Spring 是一个开源的 Java 平台,由 Rod Johnson 创建,用于简化企业级 Java 应用程序的开发。它于 2003 年首次…...
ImageButton src图片会照成内存泄露吗 会使native内存增加吗?
在Android开发中,ImageButton 是用来显示按钮的视图组件,它通常用于显示图标或图片。对于ImageButton使用的src属性(即按钮上的图片)通常不会导致内存泄漏,但是有几种情况可能会导致内存问题: 1. **不正确…...
负载均衡与容错性:集群模式在分布式系统中的应用
本文作者:小米,一个热爱技术分享的29岁程序员。如果你喜欢我的文章,欢迎关注我的微信公众号“软件求生”,获取更多技术干货! 大家好,我是小米,一个热爱分享技术的29岁程序员。今天我们来聊一聊分布式系统中的一个重要概念:集群(Cluster)模式。相信很多朋友在日常开发…...
【UE5.1 角色练习】09-物体抬升、抛出技能 - part1
前言 在上一篇(【UE5.1 角色练习】08-传送技能)的基础上继续实现控制物体抬升、抛出的功能。 效果 步骤 一、准备技能动画 1. 在项目设置中新建一个操作映射,这里命名为“Skill_GravityControl”,用按键4触发 2. 通过IK重定向…...
最大的游戏交流社区Steam服务器意外宕机 玩家服务受影响
易采游戏网6月3日消息:众多Steam游戏玩家报告称,他们无法访问Steam平台上的个人资料、好友列表和社区市场等服务。同时,社区的讨论功能也无法正常使用。经过第三方网站SteamDB的确认,,这一现象是由于Steam社区服务器突…...
如何手动批准内核扩展 Tuxera NTFS for mac内核扩展需要批准 内核扩展怎么打开
在了解如何手动批准内核扩展之前,我们应该先了解什么叫做内核扩展。内核扩展又被称为KEXT,通过它可以实现macOS系统与软件组件之间的交互,例如磁盘管理、任务管理和内存管理等等。 kext 是内核扩展(Kernel Extension)…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
