leetcode 40. 组合总和 II
题目
给定一个候选人编号的集合 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
原题链接:https://leetcode.cn/problems/combination-sum-ii/description/
思路
dfs回溯。先对 candidates 进行排序。每次选定一个数字,然后 target 减去该数字,接着继续dfs。直到找到下一个数字刚好等于剩余target,此时刚好找到一种组合;如果下一个数字大于剩余target,则直接返回。
排序主要是为了方便剪枝。作用体现在两方面:
- 当 下一个数字大于剩余target时,再下一个数字也一定大于剩余target。
- 假如当前数字之前被选过了,即不是第一次选该数字,则也可以提前剪枝,避免重复组合。
- 复杂度分析
- 时间复杂度 O(2^n)。每个数字都有选或不选的可能。
- 空间复杂度 O(n)。空间复杂度取决于递归的栈深度。
代码
class Solution {
public:vector<vector<int>> result;
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());vector<int> temp;backtrace(candidates, temp, 0, target);return result;}void backtrace(vector<int>& candidates, vector<int>& temp, int start, int target) {if (target == 0) {result.push_back(temp);return;}for (int i = start; i < candidates.size(); i++) {if (i > start && candidates[i] == candidates[i - 1]) {continue;}if (candidates[i] > target) {break;}temp.push_back(candidates[i]);backtrace(candidates, temp, i + 1, target - candidates[i]);temp.pop_back();}}
};
相关文章:
leetcode 40. 组合总和 II
题目 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 原题链接:https://leetc…...

AMEYA360代理品牌:ROHM开发出世界超小CMOS运算放大器,适用于智能手机和小型物联网设备等应用
全球知名半导体制造商ROHM(总部位于日本京都市)开发出一款超小型封装的CMOS运算放大器“TLR377GYZ”,该产品非常适合在智能手机和小型物联网设备等应用中放大温度、压力、流量等的传感器检测信号。 智能手机和物联网终端越来越小型化,这就要求搭载的元器…...

第1章Hello world 4/5:对比Rust/Java/C++创建和运行Hello world全过程:运行第一个程序
讲动人的故事,写懂人的代码 1.7 对比Rust/Java/C++创建和运行Hello world全过程 有了会听懂人类的讲话,还能做记录的编程助理艾极思,他们三人的讨论内容,都可以变成一份详细的会议纪要啦。 接下来,我们一起看看艾极思是如何记录下赵可菲创建和运行Java程序Hello world,…...
golang优雅代码【lock实现】
golang优雅代码【lock实现】 1.局部锁1.1 具体实现方式 本文代码风格来源参考 database/sql 包 更加深刻理解go语言圣经中函数是一等公民 1.局部锁 database/sql源码中使用 withLock(dc, func(){...}) 方法实现局部锁,完美利用了 golang 的 defer 关键字对 入参dc…...
Dijkstra算法(迪杰斯特拉算法)
迪杰斯特拉算法通常用在图的最短路径问题上 而迷宫的最短路径可以用BFS来做,虽然BFS不能用于带权值的迷宫,但是可以对BFS稍微改进,只需要把判断是否走过的数组改为最短路径的数组,在判断是否可走时判断是否比最短的小即可 Dijks…...

用函数指针求a和b中的大者
指针变量也可以指向一个函数。一个函数在编译时被分配给一个入口地址。这个函数入口地址就称为函数的指针。可以用一个指针变量指向函数,然后通过该指针变量调用此函数。 先按一般方法编写程序: 可以用一个指针变量指向max函数,然后通过该指…...

鸿蒙轻内核M核源码分析系列六 任务及任务调度(2)任务模块
任务是操作系统一个重要的概念,是竞争系统资源的最小运行单元。任务可以使用或等待CPU、使用内存空间等系统资源,并独立于其它任务运行。鸿蒙轻内核的任务模块可以给用户提供多个任务,实现任务间的切换,帮助用户管理业务程序流程。…...

解决找不到MSVCR120.dll,无法执行代码
msvcr120.dll是Microsoft Visual C 2013 Redistributable Package的一部分,它提供了运行使用Microsoft Visual C 2013编译器编译的程序所需的运行时环境。这个DLL文件包含了在运行使用Visual C编译器(特别是2013版)编译的应用程序时所必需的一…...

Linux iptables详解
前言:事情是这样的。最近部门在进行故障演练,攻方同学利用iptables制造了一个故障。演练最终肯定是取得了理想的效果,即业务同学在规定时间内定位了问题并恢复了业务(ps:你懂得)。 对我个人来讲一直知道iptables的存在࿰…...
Mac电脑arm64芯片Cocoapods 的 ffi 兼容问题
转载请标明出处:https://blog.csdn.net/donkor_/article/details/139505395 文章目录 前言问题分析解决方案总结 前言 今天在改Flutter项目的时候,构建IOS项目时,Cocoapods报错 Error: To set up CocoaPods for ARM macOS, run: arch -x86_6…...

如何提高逻辑性?(小妙招)
在现代社会中,逻辑性是一种至关重要的思维能力。不论是在工作、学习还是生活中,逻辑清晰的人总能更好地解决问题和做出决策。然而,如何提高逻辑性却是许多人头疼的问题。本文将从六个方面详细探讨如何提升逻辑性,包括细心态度、逼…...

2024050501-重学 Java 设计模式《实战命令模式》
重学 Java 设计模式:实战命令模式「模拟高档餐厅八大菜系,小二点单厨师烹饪场景」 一、前言 持之以恒的重要性 初学编程往往都很懵,几乎在学习的过程中会遇到各种各样的问题,哪怕别人那运行好好的代码,但你照着写完…...
0104__Linux 中 nm 命令简介
Linux 中 nm 命令简介_linux nm-CSDN博客...
Linux网络服务
01 Linux网络设置 02 DHCP原理与配置 03 DNS域名解析服务 04 远程访问及控制 05 部署YUM仓库及NFS共享服务 06 PXE高效批量网络装机...

Vue18-列表渲染
一、v-for渲染列表 1-1、遍历数组(用的多) 1-2、key属性 让每一个<li>都有一个唯一的标识! 1、写法一 只有用了遍历的方式(v-for)来生成多个同样结构的数据,必须给每个结构取一个唯一的标识。 2、写法二 或者:…...

【三维重建】增量SFM系统
在学习完鲁鹏老师的三维重建基础后,打算用C代码复现一下增量SFM系统(https://github.com/ldx-star/SFM)。 本项目的最终目标就是通过相机拍摄的多视角视图获取三维点云。由于资金有效,博主使用的是相机是小米12。 先来看一下最终…...

PyTorch 维度变换-Tensor基本操作
以如下 tensor a 为例,展示常用的维度变换操作 >>> a torch.rand(4,3,28,28) >>> a.shape torch.Size([4, 3, 28, 28])view / reshape 两者功能完全相同: a.view(shape) >>> a.view(4,3,28*28) ## a.view(4,3,28,28) 可恢复squeeze…...
spring 事务失效的几种场景
一、背景 在 springBoot 开发过程中,我们一般都是在业务方法上添加 Transactional 注解来让 spring 替我们管理事务,但在某些特定的场景下,添加完注解之后,事务是不生效的,接下来详细介绍下。 二、方法不是 public 2…...

45岁程序员独白:中年打工人出路在哪里?
作为一名也是JAVA方向的互联网从业者,我发现周围超过40岁以上的同事,基本都是部门负责人或者高层,真正还在一线做开发或者当个小领导的,已经是凤毛麟角了。 同事A今年刚满40,育有一儿一女,从进入公司到现在…...

深度探讨:为何训练精度不高却在测试中表现优异?
深度探讨:为何训练精度不高却在测试中表现优异? 在深度学习领域,我们经常遇到这样一个看似矛盾的现象:模型在训练集上的精度不是特别高,但在测试集上却能达到出色的表现。这种情况虽然不是常规,但其背后的…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...