当前位置: 首页 > 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;但其背后的…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...