当前位置: 首页 > news >正文

【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 <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 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.组合总和

组合总和 题目描述&#xff1a; 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个…...

用JS来控制遥控车(一行代码即可连接, 超简单!)

简介 有些时候我们想要做车辆的某一个功能&#xff0c;但是又不想浪费时间做整辆小车时&#xff0c;一般会去买一辆差不多的遥控车来改&#xff0c;但是那也比较麻烦&#xff0c;市面上好像也没有便宜的直接提供编程接口的遥控车。所以就自己做一个吧~。 主要是要实现向外提供…...

MyBatis-Plus如何优雅的配置多租户及分页

MyBatis-Plus如何优雅的配置多租户及分页 一、配置多租户1、步骤一2、步骤二3、步骤三步骤四 二、配置分页1、步骤一2、步骤二3、步骤三 一、配置多租户 TenantLineInnerInterceptor 是 MyBatis-Plus 提供的一个插件&#xff0c;用于实现多租户的数据隔离。通过这个插件&#…...

国产操作系统上Vim的详解01--vim基础篇 _ 统信 _ 麒麟 _ 中科方德

原文链接&#xff1a;国产操作系统上Vim的详解01–vim基础篇 | 统信 | 麒麟 | 中科方德 Hello&#xff0c;大家好啊&#xff01;今天给大家带来一篇在国产操作系统上使用Vim的详解文章。Vim是一款功能强大且高度可定制的文本编辑器&#xff0c;广泛应用于编程和日常文本编辑中。…...

如何正确理解事件溯源架构模式?

在微服务架构盛行的当下&#xff0c;DDD&#xff08;领域驱动设计&#xff09;也得到了崭新的发展。同时&#xff0c;随着DDD的不断发展&#xff0c;也诞生了一些新的设计思想和开发模式&#xff0c;今天要介绍的事件溯源是其中具有代表性的一种模式。 事件溯源模式是DDD领域中…...

【漏洞复现】电信网关配置管理系统 rewrite.php 文件上传漏洞

0x01 产品简介 中国电信集团有限公司(英文名称"China Telecom”、简称“"中国电信”)成立于2000年9月&#xff0c;是中国特大型国有通信企业、上海世博会全球合作伙伴。电信网关配置管理系统是一个用于管理和配置电信网络中网关设备的软件系统。它可以帮助网络管理员…...

线性调整率:LINE REGULATION详解

目录 一、概述 二、 举例 一、概述 LDO&#xff08;低压差线性稳压器&#xff09;的LINE REGULATION&#xff08;线路调整或线性调整&#xff09;参数是一个衡量稳压器输出稳定性的重要指标。它反映了LDO输出电压对输入电压变化的响应程度。 当输入电压在其规定的工作范围内变…...

Workfine默认首页功能详解

一、基本介绍 Workfine V6.3推出了默认的用户首页功能&#xff0c;这样用户在登入系统后就可以通过默认的首页栏进行一些业务操作。第一版的用户首页功能布局了审批&#xff0c;制单&#xff0c;业务导航&#xff0c;便捷入口&#xff0c;消息和预警六大块内容&#xff0c;后续…...

CSAPP Lab07——Malloc Lab完成思路

等不到天黑 烟火不会太完美 回忆烧成灰 还是等不到结尾 ——她说 完整代码见&#xff1a;CSAPP/malloclab-handout at main SnowLegend-star/CSAPP (github.com) Malloc Lab 按照惯例&#xff0c;我先是上来就把mm.c编译了一番&#xff0c;结果产生如下报错。搜索过后看样子应…...

简单、免费、无广告的高性能多线程文件下载工具

一、简介 1、它是一款免费、无广告的高性能多线程文件下载工具。它界面简洁&#xff0c;简单好用&#xff0c;压缩包大小仅有 0.7MB&#xff0c;目前仅支持 Windows 平台。 2、使用方法&#xff1a;点击程序左上角的【】按钮&#xff0c;将需要的链接输入进去后点击【下载】即…...

【退役之重学 SQL】什么是笛卡尔积

一、初识笛卡尔积 概念&#xff1a; 笛卡尔积是指在关系型数据库中&#xff0c;两个表进行 join 操作时&#xff0c;没有指定任何条件&#xff0c;导致生成的结果集&#xff0c;是两个表中所有行的组合。 简单来说&#xff1a; 笛卡尔积是两个表的乘积&#xff0c;结果集中的每…...

Vue3禁止 H5 界面放大与缩小功能

Vue3禁止 H5 界面放大与缩小功能 一、前言1.第一步2.第二部3.总结 一、前言 当涉及到禁止 H5 界面的放大与缩小功能时&#xff0c;Vue 3 提供了一种方便的方式来处理。我们可以使用 <script setup> 语法&#xff0c;将相关代码添加到 App.vue 组件中&#xff0c;以确保在…...

上位机图像处理和嵌入式模块部署(f407 mcu中tf卡读写和fatfs挂载)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 很早之前&#xff0c;个人对tf卡并不是很重视&#xff0c;觉得它就是一个存储工具而已。后来在移植v3s芯片的时候&#xff0c;才发现很多的soc其实…...

汽车识别项目

窗口设计 这里的代码放在py文件最前面或者最后面都无所谓 # 创建主窗口 window tk.Tk() window.title("图像目标检测系统") window.geometry(1000x650) # 设置窗口大小# 创建背景画布并使用grid布局管理器 canvas_background tk.Canvas(window, width1000, height…...

【面试题-012】什么是Spring 它有哪些优势

文章目录 Spring有哪些优势有哪些优势Spring和Springboot区别在 Spring 框架中&#xff0c;什么是AOP核心概念应用场景 Spring有哪些通知类型 Spring 是一个开源的 Java 平台&#xff0c;由 Rod Johnson 创建&#xff0c;用于简化企业级 Java 应用程序的开发。它于 2003 年首次…...

ImageButton src图片会照成内存泄露吗 会使native内存增加吗?

在Android开发中&#xff0c;ImageButton 是用来显示按钮的视图组件&#xff0c;它通常用于显示图标或图片。对于ImageButton使用的src属性&#xff08;即按钮上的图片&#xff09;通常不会导致内存泄漏&#xff0c;但是有几种情况可能会导致内存问题&#xff1a; 1. **不正确…...

负载均衡与容错性:集群模式在分布式系统中的应用

本文作者:小米,一个热爱技术分享的29岁程序员。如果你喜欢我的文章,欢迎关注我的微信公众号“软件求生”,获取更多技术干货! 大家好,我是小米,一个热爱分享技术的29岁程序员。今天我们来聊一聊分布式系统中的一个重要概念:集群(Cluster)模式。相信很多朋友在日常开发…...

【UE5.1 角色练习】09-物体抬升、抛出技能 - part1

前言 在上一篇&#xff08;【UE5.1 角色练习】08-传送技能&#xff09;的基础上继续实现控制物体抬升、抛出的功能。 效果 步骤 一、准备技能动画 1. 在项目设置中新建一个操作映射&#xff0c;这里命名为“Skill_GravityControl”&#xff0c;用按键4触发 2. 通过IK重定向…...

最大的游戏交流社区Steam服务器意外宕机 玩家服务受影响

易采游戏网6月3日消息&#xff1a;众多Steam游戏玩家报告称&#xff0c;他们无法访问Steam平台上的个人资料、好友列表和社区市场等服务。同时&#xff0c;社区的讨论功能也无法正常使用。经过第三方网站SteamDB的确认&#xff0c;&#xff0c;这一现象是由于Steam社区服务器突…...

如何手动批准内核扩展 Tuxera NTFS for mac内核扩展需要批准 内核扩展怎么打开

在了解如何手动批准内核扩展之前&#xff0c;我们应该先了解什么叫做内核扩展。内核扩展又被称为KEXT&#xff0c;通过它可以实现macOS系统与软件组件之间的交互&#xff0c;例如磁盘管理、任务管理和内存管理等等。 kext 是内核扩展&#xff08;Kernel Extension&#xff09;…...

智慧树自动刷课插件:3分钟安装的终极学习效率提升指南

智慧树自动刷课插件&#xff1a;3分钟安装的终极学习效率提升指南 【免费下载链接】zhihuishu 智慧树刷课插件&#xff0c;自动播放下一集、1.5倍速度、无声 项目地址: https://gitcode.com/gh_mirrors/zh/zhihuishu 还在为智慧树平台的冗长视频课程烦恼吗&#xff1f;智…...

如何实现虚拟游戏控制器:ViGEmBus驱动完整技术解析

如何实现虚拟游戏控制器&#xff1a;ViGEmBus驱动完整技术解析 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus ViGEmBus是一款专业的Windows内核模式驱动&am…...

OpenVAS部署避坑指南:从Kali的`apt-get install gvm`到官方OVA镜像,我踩过的那些雷

OpenVAS部署避坑指南&#xff1a;从Kali的apt-get install gvm到官方OVA镜像实战复盘 1. 为什么OpenVAS部署总让人头疼&#xff1f; 三年前我第一次接触漏洞扫描工具时&#xff0c;OpenVAS的安装过程就给我留下了深刻印象。当时按照某技术论坛的教程&#xff0c;在Kali Linux…...

GTA5终极防护与增强指南:YimMenu完整使用教程

GTA5终极防护与增强指南&#xff1a;YimMenu完整使用教程 【免费下载链接】YimMenu YimMenu, a GTA V menu protecting against a wide ranges of the public crashes and improving the overall experience. 项目地址: https://gitcode.com/GitHub_Trending/yi/YimMenu …...

从游戏动作到影视特效:Blender Python骨骼动画脚本的跨界实战指南

从游戏动作到影视特效&#xff1a;Blender Python骨骼动画脚本的跨界实战指南 在数字内容创作领域&#xff0c;骨骼动画是连接游戏开发与影视特效的核心技术纽带。无论是独立游戏开发者需要将角色动作导出到Unity引擎&#xff0c;还是影视动画师希望批量处理动作捕捉数据&#…...

ADAU1701 DSP资源极限探索:从31段EQ到内存溢出,手把手教你做性能压力测试

ADAU1701 DSP资源极限探索&#xff1a;从31段EQ到内存溢出的性能压力测试方法论 在音频处理领域&#xff0c;ADAU1701作为一款经典的DSP芯片&#xff0c;其资源分配与性能边界一直是开发者关注的焦点。当客户提出"能否实现90段EQ"这类需求时&#xff0c;仅凭数据手册…...

从攻到防:手把手在Kali Linux上搭建ARP欺骗实验环境(含Wireshark分析)

构建安全的本地网络实验室&#xff1a;Kali Linux下ARP欺骗攻防实战指南 在网络安全领域&#xff0c;理解攻击原理是构建有效防御的第一步。ARP欺骗作为一种经典的中间人攻击技术&#xff0c;常被用于网络渗透测试中。本文将带你从零开始搭建一个完全隔离的虚拟实验环境&#x…...

告别串口助手!用手机APP和ESP-01S模块,5分钟搞定51单片机无线控制LED

手机APP直连ESP-01S&#xff1a;零门槛实现51单片机LED无线控制 在物联网原型开发中&#xff0c;摆脱串口助手的束缚&#xff0c;直接用手机APP控制硬件设备&#xff0c;是许多初学者的迫切需求。本文将带你用最常见的ESP-01S模块和任意一款TCP调试APP&#xff0c;在5分钟内搭建…...

从RTL到GDS:STA工程师的一天,如何用DC工具修复时序违例(以Setup Violation为例)

从RTL到GDS&#xff1a;STA工程师的一天&#xff0c;如何用DC工具修复时序违例&#xff08;以Setup Violation为例&#xff09; 时钟刚过上午9点&#xff0c;咖啡的香气弥漫在工位周围。作为数字后端工程师&#xff0c;我习惯在晨会前先快速扫描昨晚综合运行的日志文件。今天的…...

城市网格化治理平台

在快速城市化的今天&#xff0c;传统的“治安维护”模式已经远远不够。如何利用有限的治理资源&#xff0c;最大化地覆盖城市的每一个角落&#xff1f;答案就在于网格化。所谓网格化治理&#xff0c;即将城市空间划分为若干个均匀的“网格”&#xff0c;每一个网格都有明确的边…...