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

leetcode 40. 组合总和 II

题目

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意:解集不能包含重复的组合。

原题链接:https://leetcode.cn/problems/combination-sum-ii/description/

思路

dfs回溯。先对 candidates 进行排序。每次选定一个数字,然后 target 减去该数字,接着继续dfs。直到找到下一个数字刚好等于剩余target,此时刚好找到一种组合;如果下一个数字大于剩余target,则直接返回。
排序主要是为了方便剪枝。作用体现在两方面:

  1. 当 下一个数字大于剩余target时,再下一个数字也一定大于剩余target。
  2. 假如当前数字之前被选过了,即不是第一次选该数字,则也可以提前剪枝,避免重复组合。
  • 复杂度分析
    • 时间复杂度 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 &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意&#xff1a;解集不能包含重复的组合。 原题链接&#xff1a;https://leetc…...

AMEYA360代理品牌:ROHM开发出世界超小CMOS运算放大器,适用于智能手机和小型物联网设备等应用

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

第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(){...}) 方法实现局部锁&#xff0c;完美利用了 golang 的 defer 关键字对 入参dc…...

Dijkstra算法(迪杰斯特拉算法)

迪杰斯特拉算法通常用在图的最短路径问题上 而迷宫的最短路径可以用BFS来做&#xff0c;虽然BFS不能用于带权值的迷宫&#xff0c;但是可以对BFS稍微改进&#xff0c;只需要把判断是否走过的数组改为最短路径的数组&#xff0c;在判断是否可走时判断是否比最短的小即可 Dijks…...

用函数指针求a和b中的大者

指针变量也可以指向一个函数。一个函数在编译时被分配给一个入口地址。这个函数入口地址就称为函数的指针。可以用一个指针变量指向函数&#xff0c;然后通过该指针变量调用此函数。 先按一般方法编写程序&#xff1a; 可以用一个指针变量指向max函数&#xff0c;然后通过该指…...

鸿蒙轻内核M核源码分析系列六 任务及任务调度(2)任务模块

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

解决找不到MSVCR120.dll,无法执行代码

msvcr120.dll是Microsoft Visual C 2013 Redistributable Package的一部分&#xff0c;它提供了运行使用Microsoft Visual C 2013编译器编译的程序所需的运行时环境。这个DLL文件包含了在运行使用Visual C编译器&#xff08;特别是2013版&#xff09;编译的应用程序时所必需的一…...

Linux iptables详解

前言&#xff1a;事情是这样的。最近部门在进行故障演练&#xff0c;攻方同学利用iptables制造了一个故障。演练最终肯定是取得了理想的效果&#xff0c;即业务同学在规定时间内定位了问题并恢复了业务(ps&#xff1a;你懂得)。 对我个人来讲一直知道iptables的存在&#xff0…...

Mac电脑arm64芯片Cocoapods 的 ffi 兼容问题

转载请标明出处&#xff1a;https://blog.csdn.net/donkor_/article/details/139505395 文章目录 前言问题分析解决方案总结 前言 今天在改Flutter项目的时候&#xff0c;构建IOS项目时&#xff0c;Cocoapods报错 Error: To set up CocoaPods for ARM macOS, run: arch -x86_6…...

如何提高逻辑性?(小妙招)

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

2024050501-重学 Java 设计模式《实战命令模式》

重学 Java 设计模式&#xff1a;实战命令模式「模拟高档餐厅八大菜系&#xff0c;小二点单厨师烹饪场景」 一、前言 持之以恒的重要性 初学编程往往都很懵&#xff0c;几乎在学习的过程中会遇到各种各样的问题&#xff0c;哪怕别人那运行好好的代码&#xff0c;但你照着写完…...

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、遍历数组&#xff08;用的多&#xff09; 1-2、key属性 让每一个<li>都有一个唯一的标识&#xff01; 1、写法一 只有用了遍历的方式(v-for)来生成多个同样结构的数据&#xff0c;必须给每个结构取一个唯一的标识。 2、写法二 或者&#xff1a;…...

【三维重建】增量SFM系统

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

PyTorch 维度变换-Tensor基本操作

以如下 tensor a 为例&#xff0c;展示常用的维度变换操作 >>> 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 开发过程中&#xff0c;我们一般都是在业务方法上添加 Transactional 注解来让 spring 替我们管理事务&#xff0c;但在某些特定的场景下&#xff0c;添加完注解之后&#xff0c;事务是不生效的&#xff0c;接下来详细介绍下。 二、方法不是 public 2…...

45岁程序员独白:中年打工人出路在哪里?

作为一名也是JAVA方向的互联网从业者&#xff0c;我发现周围超过40岁以上的同事&#xff0c;基本都是部门负责人或者高层&#xff0c;真正还在一线做开发或者当个小领导的&#xff0c;已经是凤毛麟角了。 同事A今年刚满40&#xff0c;育有一儿一女&#xff0c;从进入公司到现在…...

深度探讨:为何训练精度不高却在测试中表现优异?

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

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 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开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

OPENCV形态学基础之二腐蚀

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

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...