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

40. 组合总和 II(力扣LeetCode)

文章目录

  • 40. 组合总和 II
    • 题目描述
    • 回溯算法

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

回溯算法

// 定义一个Solution类,用于解决组合总和II问题
class Solution {
public:// 定义一个公共方法combinationSum2,它接受一个整数数组candidates和一个整数target,// 返回一个二维整数数组,里面包含了所有可以使数字和为target的组合。vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {// 首先对数组进行排序,这会帮助我们更容易地找到组合,并且能够跳过重复的组合sort(candidates.begin(),candidates.end());// 输出排序后的数组元素,这一步通常是为了调试for(int i=0;i<candidates.size();i++)cout<<candidates[i]<<" ";// 定义一个布尔向量used,用于标记candidates中的元素是否被用在当前的组合中vector<bool> used(candidates.size(),false);// 调用backstracking函数,开始回溯算法backstracking(candidates, target, 0, 0, used);// 返回所有找到的组合return result;}private:// 定义一个私有变量result,用于存储所有找到的组合vector<vector<int>> result;// 定义一个私有变量path,用于存储当前正在考虑的组合vector<int> path;// 定义一个私有函数backstracking,它实现了回溯算法void backstracking(vector<int>& candidates,int target,int sum,int start,vector<bool>& used){// 如果当前组合的数字和大于目标数target,则当前路径不可能为解,回溯if(sum>target)return;// 如果当前组合的数字和等于目标数target,则找到了一个解,将它添加到result中if(sum==target){result.push_back(path);return;}// 从start开始遍历candidates数组,尝试每个可能的元素for(int i=start;i<candidates.size();i++){// 跳过重复的数字,以避免重复的组合,这是因为数组已经排序if(i>0 && candidates[i]==candidates[i-1] && !used[i-1])continue;// 将candidates[i]添加到当前路径path.push_back(candidates[i]);// 标记该元素为已使用used[i]=true;// 将candidates[i]的值加到当前和上,并递归调用backstracking,注意新的start是i+1,因为每个数字只能使用一次sum+=candidates[i];backstracking(candidates, target, sum, i+1, used);// 回溯,将最后一个元素从路径中删除并从当前和中减去,取消标记该元素path.pop_back();used[i]=false;// 从当前和中减去candidates[i]的值,为下一次迭代准备sum-=candidates[i];}}
};

代码主要由以下几个部分组成:

  • combinationSum2 公共方法:对给定数组排序,初始化用于记录元素使用情况的布尔向量,开始回溯搜索,最后返回结果。
  • backstracking 私有方法:实现了回溯算法的核心逻辑,通过递归尝试每个可能的元素,直到找到所有的组合或者终止搜索。
  • result 和 path 私有变量:分别用于存储找到的所有组合结果和当前递归路径中的组合。
  • used 布尔向量:用于标记数组 candidates 中的元素是否已经被使用过,以防止在同一路径中重复使用。

相关文章:

40. 组合总和 II(力扣LeetCode)

文章目录 40. 组合总和 II题目描述回溯算法 40. 组合总和 II 题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意&#xff…...

Ubuntu上Jenkins自动化部署Gitee上SpringBoot项目

文章目录 安装安装JDK安装Maven安装GitNodeJS安装&#xff08;可选&#xff09;安装Jenkins 配置Jenkins为Jenkins更换插件源设置jenkins时区安装插件全局工具配置添加Gitee凭证Gitee项目配置 部署后端1.新建任务2.配置源码管理3.构建触发器4.到Gitee中添加WebHook5.构建环境6.…...

延迟任务基于DeyalQueue

一&#xff0c;延迟任务应用场景&#xff1f; 一般用于处理订单&#xff0c;将redis中的数据延迟存入数据库&#xff0c;实现异步存储减少DB的压力 二&#xff0c; 延迟任务的实现方案有很多 DelayQueue Redisson MQ 时间轮 原理 JDK自带延迟队列&#xff0c;基于阻塞队列…...

Linux 查询端口被占用命令

Linux 查询端口被占用命令 1、lsof -i:端口号 用于查看某一端口的占用情况&#xff0c;比如查看8000端口使用情况&#xff0c;lsof -i:8000 lsof -i:8080&#xff1a;查看8080端口占用 lsof abc.txt&#xff1a;显示开启文件abc.txt的进程 lsof -c abc&#xff1a;显示abc进…...

【c++】string类---标准库中的string类

1. 为什么要学习string类 1.1 C语言中的字符串 C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列 库函数&#xff0c;但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP的思想&#xff0c;而且…...

GO语言学习笔记(与Java的比较学习)(五)

Map 概念 map 是引用类型&#xff0c;可以使用如下声明&#xff1a; var map1 map[keytype]valuetype var map1 map[string]int 在声明的时候不需要知道 map 的长度&#xff0c;map 是可以动态增长的。 未初始化的 map 的值是 nil&#xff08;即零值为nil&#xff09;&…...

Sora:探索大型视觉模型的前世今生、技术内核及未来趋势

Sora&#xff0c;一款由OpenAI在2024年2月推出的创新性文生视频的生成式AI模型&#xff0c;能够依据文字说明&#xff0c;创作出既真实又富有想象力的场景视频&#xff0c;展现了其在模拟现实世界方面的巨大潜能。本文基于公开技术文档和逆向工程分析&#xff0c;全面审视了Sor…...

基于springboot实现图书馆管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现图书馆管理系统演示 摘要 电脑的出现是一个时代的进步&#xff0c;不仅仅帮助人们解决了一些数学上的难题&#xff0c;如今电脑的出现&#xff0c;更加方便了人们在工作和生活中对于一些事物的处理。应用的越来越广泛&#xff0c;通过互联网我们可以更方便地…...

MATLAB环境下基于高斯滤波器-广义拉普拉斯算子的细胞核自动检测

作为病理图像分析的基础&#xff0c;细胞核检测可为细胞形态、纹理等多种相关分析提供支持&#xff0c;对于临床诊断具有重要意义。但是细胞核的人工识别过程十分费时费力&#xff0c;并且不同医生之间存在主观标注差异。因此&#xff0c;利用计算机技术进行自动检测能够更为客…...

【探索AI】十一 深度学习之第1周:深度学习概述与基础

深度学习概述与基础 深度学习的发展历史与现状神经网络的基本原理前向传播与反向传播算法常见的激活函数与优化算法深度学习框架&#xff08;如TensorFlow或PyTorch&#xff09;进行基础操作 深度学习的发展历史与现状 深度学习的发展历史可以追溯到上世纪40年代&#xff0c;当…...

【简说八股】Spring事务失效可能是哪些原因?

Spring事务介绍 Spring事务是指在Spring框架中对数据库操作进行管理的一种机制&#xff0c;它确保一组数据库操作要么完全执行成功&#xff08;提交&#xff09;&#xff0c;要么完全不执行&#xff08;回滚&#xff09;&#xff0c;从而保持数据一致性和完整性。 Spring框架…...

【语音识别】- CTC损失计算的原理

文章目录 1.符号定义与目标函数2.前向计算 α s ( t ) \alpha_s(t) α...

MySQL字符集和比较规则

MySQL字符集和比较规则 字符集和比较规则简介 字符集&#xff1a; 描述字符与二进制数据的映射关系 比较规则&#xff1a;比较指定字符集中的字符的规则 字符集 我们知道&#xff0c;计算机无法直接存储字符串&#xff0c;实际存储的都是二进制数据。字符集是有限的&#xff…...

备忘录模式(Memento Pattern)

定义 备忘录模式&#xff08;Memento Pattern&#xff09;是一种行为设计模式&#xff0c;它允许在不破坏封装性的前提下捕获一个对象的内部状态&#xff0c;并在以后将对象恢复到该状态。备忘录模式通常用于实现撤销操作&#xff08;Undo&#xff09;或历史记录&#xff08;H…...

LeetCode 刷题 [C++] 第121题.买卖股票的最佳时机

题目描述 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的…...

ORACLE 基础

一.ORACLE简介 1.1什么是oracle ORACLE 数据库系统是美国 ORACLE 公司&#xff08;甲骨文&#xff09;提供的以分布式数据库为核心的一组软件产品&#xff0c;是目前最流行的客户/服务器(CLIENT/SERVER)或 B/S 体系结构的数据库之一。 ORACLE 通常应用于大型系统的数据库产品。…...

Adobe illustrator CEP插件调试

1.创建插件CEP面板&#xff0c;可以参考&#xff1a;http://blog.nullice.com/%E6%8A%80%E6%9C%AF/CEP-%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8B/%E6%8A%80%E6%9C%AF-CEP-%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8B-Adobe-CEP-%E6%89%A9%E5%B1%95%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8…...

学会玩游戏,智能究竟从何而来?

最近在读梅拉妮米歇尔《AI 3.0》第三部分第九章&#xff0c;谈到学会玩游戏&#xff0c;智能究竟从何而来&#xff1f; 作者: [美] 梅拉妮米歇尔 出版社: 四川科学技术出版社湛庐 原作名: Artificial Intelligence: A Guide for Thinking Humans 译者: 王飞跃 / 李玉珂 / 王晓…...

Unity 常用操作

2D素材网站 https://craftpix.net/ https://itch.io/game-assets/tag-2d/tag-backgrounds 3D素材资源网址 https://www.mixamo.com/#/ 场景常用操作&#xff1a; 快捷键&#xff1a;QWER Q&#xff1a;Q键或鼠标中键&#xff0c;可以拉动场景。 W&#xff1a;选中物体后&…...

【计算机网络_应用层】协议定制序列化反序列化

文章目录 1. TCP协议的通信流程2. 应用层协议定制3. 通过“网络计算器”的实现来实现应用层协议定制和序列化3.1 protocol3.2 序列化和反序列化3.2.1 手写序列化和反序列化3.2.2 使用Json库 3.3 数据包读取3.4 服务端设计3.5 最后的源代码和运行结果 1. TCP协议的通信流程 在之…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...