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

每天一道算法题:40. 组合总和 II

难度

中等

题目

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次
注意:解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

思路

和 39 题类似但是不能有重复的解,使用回溯试探法,但是过程要考虑去重。
数组中可能出现重复的数字,但是结果中不能出现重复的解,在处理过程中就要进行去重和剪枝。首先对 candidates 数组进行排序,在递归的过程中,当发现当前元素与前一个元素相同,并且前一个元素已经被考虑过(不在当前组合中),就跳过当前元素。
从数组的第一个元素开始,依次考虑是否选择该元素,再递归地考虑下一个元素,每个数字只能使用一次,因此在递归调用时,下一轮搜索的起始位置应该是当前位置的下一个位置。

代码

"""
10,1,2,7,6,1,5
8如果不排序的情况(10) > 8
1 2 7 > 8
1 2 6 > 8
1 2 1 5 > 8
1 2 5 = 81 7   = 8
1 6 1 = 8
1 1 5 遍历完成
1 5   遍历完成2 7   > 8
2 6   = 8
2 1 5 = 8 重复了 去重的方法 就是将所有的子集排序后,再进行去重,这样是再将所有的接过遍历完成之后,才能去重,效率非常低
2 52 7 > 8
2 6 = 8
2"""class Solution:def combinationSum2(self, candidates, target):self.candidates = candidates# 先对所有元素进行排序,再递归过程中进行去重,如果相邻的两个值相同,并且前一个值已经选过了,就不会选self.candidates.sort()self.target = targetself.length = len(self.candidates)self.cache = []self.result = []self.backtrack(0, [], self.target)print(self.result)return self.resultdef backtrack(self, start, tmp, target):# start 在当前层遍历的开始位置# tmp 记录临时值的栈# target 目标值,当目标值为0是 就可以终止递归# 当目标值为0的时候就终止递归,记录此时的组合if target == 0:self.result.append(tmp[:])returnfor i in range(start, self.length):# 在同一层遍历的时候,如果两个相邻的元素相同,就跳过 使用i-1就说明 上一个位置的值已经被选过了# i > start 因为要和前一个元素比较,所以i的值必须时大于start的,不然会越界if i > start and self.candidates[i] == self.candidates[i - 1]:continue# 如果当前值比目标值小 或者 相等的时候,才去递归下一层,不然直接跳过if target >= self.candidates[i]:tmp.append(self.candidates[i])# 集合中 每各元素只能添加一次,所以添加完当前的元素后,去下一层试探的时候只能从下一位开始遍历,所以下一层的开始位置就是i+1self.backtrack(i + 1, tmp, target - self.candidates[i])tmp.pop()if __name__ == '__main__':candidates = [10, 1, 2, 7, 6, 1, 5]target = 8# candidates = [2, 5, 2, 1, 2]# target = 5s = Solution()s.combinationSum2(candidates, target)

相关文章:

每天一道算法题:40. 组合总和 II

难度 中等 题目 给定一个候选人编号的集合 candidates 和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意&#xff1a;解集不能包含重复的组合。 示例 1: 输入: candidat…...

Centos7安装PostgreSQL 14

环境&#xff1a; Centos7安装PostgreSQL_14版本数据库&#xff1b; 打开官方网站&#xff1a;PostgreSQL: Linux downloads (Red Hat family) 一、 版本选择 复制、粘贴并运行如下脚本&#xff1a; 二、安装步骤 这些命令是在 CentOS 7.x 系统上安装和配置 PostgreSQL 14 的步…...

Shopee的折扣活动怎么分类?shopee设置折扣注意事项

旺季到来&#xff0c;Shopee会举办一些折扣活动来吸引客户&#xff0c;那么shopee的折扣活动怎么分类&#xff0c;shopee设置折扣注意事项&#xff1f; shopee的折扣活动怎么分类&#xff1f; 满减活动&#xff1a;满减活动是虾皮常见的一种折扣形式。在这种活动中&#xff0…...

磁盘空间占用巨大的meta.db-wal文件缓存(tracker-miner-fs索引服务)彻底清除办法

磁盘命令参考本博客linux磁盘空间满了怎么办. 问题: 磁盘空间被盗 今天瞄了一下我的Ubuntu系统盘&#xff0c; nftdiggernftdigger-Ubuntu:~$ df -h 文件系统 容量 已用 可用 已用% 挂载点 udev 16G 0 16G 0% /dev tmpfs 3.2G 1.9…...

力扣:160. 相交链表(Python3)

题目&#xff1a; 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;…...

【华为OD机试AB高分必刷题目】无名的搜索题(Java-优先搜索(DFS)实现)

🚀你的旅程将在这里启航!本专栏所有题目均包含优质解题思路,高质量解题代码,详细代码讲解,助你深入学习,高分通过! 文章目录 【华为OD机试AB高分必刷题目】无名的搜索题(Java-优先搜索(DFS)实现)题目描述解题思路Java题解代码代码OJ评判结果代码讲解寄语【华为OD机…...

ant 任务(task)通过内嵌的arg元素传递命令行参数

有的ant 任务将参数传递给其它的进程作为命令行参数。这可以通过内嵌的arg元素来实现。 例如&#xff1a; <exec executable"${browser}" spawn"true"><arg value"${file}"/> </exec>arg元素的部分属性说明&#xff1a; val…...

STM32G0+EMW3080+阿里云飞燕平台实现单片机WiFi智能联网功能(三)STM32G0控制EMW3080实现IoT功能

项目描述&#xff1a;该系列记录了STM32G0EMW3080实现单片机智能联网功能项目的从零开始一步步的实现过程&#xff1b;硬件环境&#xff1a;单片机为STM32G030C8T6&#xff1b;物联网模块为EMW3080V2-P&#xff1b;网联网模块的开发板为MXKit开发套件&#xff0c;具体型号为XCH…...

IntelliJ IDEA - Git Commit 后 Commit 窗口不消失解决方案

这个现象是在 2023 年版本后开始的&#xff0c;一开始以为是 Mac 系统的原因&#xff0c;后来发现原来 Windows 也这样&#xff0c;所以应该只跟 IDEA 版本有关 可以看到左侧 commit 后&#xff0c;这个侧边栏还在&#xff0c;按理讲在以前的版本是之前消失&#xff0c;这样使…...

Vue 组件化编程 和 生命周期

目录 一、组件化编程 1.基本介绍 : 2.原理示意图 : 3.全局组件示例 : 4.局部组件示例 : 5.全局组件和局部组件的区别 : 二、生命周期 1.基本介绍 : 2.生命周期示意图 : 3.实例测试 : 一、组件化编程 1.基本介绍 : (1) 开发大型应用的时候&#xff0c;页面往往划分成…...

《数字图像处理-OpenCV/Python》连载(41)图像的旋转

《数字图像处理-OpenCV/Python》连载&#xff08;41&#xff09;图像的旋转 本书京东优惠购书链接&#xff1a;https://item.jd.com/14098452.html 本书CSDN独家连载专栏&#xff1a;https://blog.csdn.net/youcans/category_12418787.html 第 6 章 图像的几何变换 几何变换分…...

案例 - 拖拽上传文件,生成缩略图

直接看效果 实现代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>拖拽上传文件</title>&l…...

PHP 使用递归方式 将其二维数组整合为层级树 其中层级id 为一个uuid的格式 造成的诡异问题 已解决

不啰嗦 直接上源代码 <?php function findChildren($list, $p_id){$r array();foreach ($list as $k > $item) {if ($item[fid] $p_id) {unset($list[$k]);$length count($r);$r[$length] $item;if ($t findChildren($list, $item[id])) {$r[$length][children] …...

rv1126-rv1109-添加分区,定制固件,开机挂载功能

===================================================================== 修改分区: 这里是分区的txt文件选择; 这里是分区的划分,我这里回车了,方便看 FIRMWARE_VER: 8.1 MACHINE_MODEL: RV1126 MACHINE_ID: 007 MANUFACTURER: RV1126 MAGIC: 0x5041524B ATAG: 0x00200…...

一台电脑使用多个gitee账号,以及提交忽略部分文件

目录 ​编辑 一&#xff1a;前言 二&#xff1a;解决方法 三&#xff1a;提交gitee时忽略文件 一&#xff1a;前言 在开发中&#xff0c;我们拥有不止一个 gitee 账号&#xff0c;通常而言一个是公司的&#xff0c;一个是私人的。有时候我们在公司写了一些自己的东西&#…...

解析邮件文本内容; Mime文本解析; MimeStreamParser; multipart解析

原始文本 ------_Part_46705_715015081.1699589700255 Content-Type: text/html;charsetUTF-8 Content-Transfer-Encoding: base64PGh0bWwCiAgICA8aGVhZD4KICAgICAgICA8bWV0YSBodHRwLW VxdWl2PSJDb250ZW50LVR5cGUiIGNvbnRlbnQ9InRleHQvaHRt bDsgY2hhcnNldD1VVEYtOCICiAgICAgIC…...

获取请求IP以及IP解析成省份

某些业务需要获取请求IP以及将IP解析成省份之类的&#xff0c;于是我写了一个工具类&#xff0c;可以直接COPY /*** IP工具类* author xxl* since 2023/11/9*/ Slf4j public class IPUtils {/*** 过滤本地地址*/public static final String LOCAL_ADDRESS "127.0.0.1&quo…...

YOLOv8-seg改进:复现HIC-YOLOv5,HIC-YOLOv8-seg助力小目标分割

🚀🚀🚀本文改进:HIC-YOLOv8-seg:1)添加一个针对小物体的额外预测头,以提供更高分辨率的特征图2)在backbone和neck之间采用involution block来增加特征图的通道信息;3)在主干网末端加入 CBAM 的注意力机制; 🚀🚀🚀HIC-YOLOv8-seg小目标分割检测&复杂场景…...

vscode 终端进程启动失败: shell 可执行文件“C:\Windows\System32\WindowsPower

vscode 终端进程启动失败: shell 可执行文件“C:\Windows\System32\WindowsPower 第一次用vscode&#xff0c;然后遇到这个问题&#xff0c;在设置里搜索 terminal.integrated.defaultProfile.windows 将这里的null改成"Command Prompt" 重启就可以了...

【中间件篇-Redis缓存数据库02】Redis高级特性和应用(慢查询、Pipeline、事务、Lua)

Redis高级特性和应用(慢查询、Pipeline、事务、Lua) Redis的慢查询 许多存储系统&#xff08;例如 MySQL)提供慢查询日志帮助开发和运维人员定位系统存在的慢操作。所谓慢查询日志就是系统在命令执行前后计算每条命令的执行时间&#xff0c;当超过预设阀值,就将这条命令的相关…...

Spyder 5新版本尝鲜指南:从界面汉化到高效调试,你的数据分析IDE该升级了

Spyder 5新版本尝鲜指南&#xff1a;从界面汉化到高效调试&#xff0c;你的数据分析IDE该升级了 如果你还在用老版本的Spyder处理数据分析工作&#xff0c;那么现在可能是时候考虑升级了。Spyder 5带来了诸多令人惊喜的改进&#xff0c;从更流畅的界面体验到更强大的调试功能&a…...

XUnity自动翻译器:5分钟让Unity游戏变身中文版

XUnity自动翻译器&#xff1a;5分钟让Unity游戏变身中文版 【免费下载链接】XUnity.AutoTranslator 项目地址: https://gitcode.com/gh_mirrors/xu/XUnity.AutoTranslator 还在为看不懂的外语游戏而烦恼吗&#xff1f;XUnity自动翻译器是你的终极解决方案&#xff01;这…...

Vue H5移动端应用集成NFC读取功能的实战解析

1. 为什么要在Vue H5应用中集成NFC功能&#xff1f; 最近两年&#xff0c;越来越多的线下场景开始使用NFC技术。比如商场里的智能货架、博物馆的电子讲解牌、会议签到系统等等。作为一个Vue开发者&#xff0c;我发现很多客户都希望在他们的H5应用中加入NFC读取功能&#xff0c…...

Spring AI ETL进阶:定制中文元数据增强与Milvus向量化存储实战

1. Spring AI ETL的核心价值与应用场景 在处理中文文本数据时&#xff0c;传统的ETL流程常常会遇到语义理解不准确、上下文丢失等问题。Spring AI提供的ETL框架通过模块化设计&#xff0c;让开发者能够轻松构建适合中文场景的数据处理流水线。我最近在一个知识库项目中实际应用…...

CN3130 可用太阳能板供电的纽扣电池充电管理芯片

概述&#xff1a; CN3130是可以用太阳能板供电的可充电纽扣电池充电管理芯片。该器件内部包括功率晶体管&#xff0c;应 用时不需要外部的电流检测电阻和阻流二极管。 内部的充电电流自适应模块能够根据输入电源的电流输出能力自动调整充电电流&#xff0c;用户不需要考 虑最坏…...

造相-Z-Image常见问题解决:RTX 4090部署、生成、优化全攻略

造相-Z-Image常见问题解决&#xff1a;RTX 4090部署、生成、优化全攻略 如果你手握一块性能强劲的RTX 4090显卡&#xff0c;却总在运行文生图模型时遇到显存爆满、生成黑图、速度缓慢的困扰&#xff0c;那么这篇文章就是为你准备的。造相-Z-Image&#xff0c;一个专为RTX 4090…...

保姆级教学:Sambert多情感语音合成镜像部署与使用全攻略

保姆级教学&#xff1a;Sambert多情感语音合成镜像部署与使用全攻略 1. 准备工作&#xff1a;了解Sambert语音合成镜像 Sambert多情感中文语音合成镜像是一个开箱即用的语音生成解决方案&#xff0c;基于阿里达摩院研发的Sambert-HiFiGAN模型构建。这个镜像已经预先解决了常见…...

GLM-OCR模型Java开发集成指南:SpringBoot微服务中的文档处理实战

GLM-OCR模型Java开发集成指南&#xff1a;SpringBoot微服务中的文档处理实战 最近在做一个企业内部的文档管理系统&#xff0c;客户提了个需求&#xff0c;说能不能自动把上传的发票、合同这些图片里的文字给提取出来&#xff0c;省得人工一个个去敲。这需求听着就挺实在的&am…...

手把手教你用DSP28335驱动W5500实现TCP客户端(附完整代码与避坑指南)

DSP28335与W5500以太网通信实战&#xff1a;从硬件连接到稳定数据传输 在工业自动化、远程监控和智能设备领域&#xff0c;嵌入式系统联网已成为刚需。TI的DSP28335凭借其强大的实时处理能力&#xff0c;结合W5500这款硬连线TCP/IP协议栈芯片&#xff0c;能够为设备赋予稳定可靠…...

SystemVerilog Clocking Block实战:从接口同步到Verdi Delta Cycle调试

1. SystemVerilog Clocking Block基础解析 Clocking Block是SystemVerilog中用于接口同步的核心语法结构&#xff0c;它本质上是一个时序控制单元&#xff0c;能够精确管理信号采样和驱动的时序关系。想象一下&#xff0c;这就像在繁忙的十字路口设置红绿灯&#xff0c;确保不同…...