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

leetcode第40题组合总和Ⅱ

原题出于leetcode第40题https://leetcode.cn/problems/combination-sum-ii/题目如下:

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

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

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

1树型结构

这里引入两个概念——树枝去重和树层去重,因为元素不可重复读取且不能有重复组合,因此我们只需处理树层去重,如上图所示。去重代码如下:

if(i>0 && candidate[i]==candidate[i-1] && used[i-1]==0) continue;

2代码

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& candidates,int target,int sum,int startindex,vector<bool>& used){if(sum>target) return ;if(sum==target){result.push_back(path); return;          }for(int i=startindex;i<candidates.size();i++){if(i>0 &&candidates[i]==candidates[i-1]&& used[i-1]==0)continue;sum+=candidates[i];path.push_back(candidates[i]);used[i]=true;backtracking(candidates,target,sum,i+1,used);sum-=candidates[i];path.pop_back();used[i]=false;}return ;}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {int n=candidates.size();vector<bool>used(n,0);path.clear();result.clear();sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used); return result;       }
};

以上树型结构的图片出自代码随想录

相关文章:

leetcode第40题组合总和Ⅱ

原题出于leetcode第40题https://leetcode.cn/problems/combination-sum-ii/题目如下&#xff1a; 给定一个候选人编号的集合 candidates &#xff08;candidate中有重复的元素&#xff09;和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合…...

迷你世界脚本状态接口:Buff

状态接口&#xff1a;Buff 迷你世界 更新时间: 2023-04-26 20:07:54 具体函数名及描述如下: 序号 函数名 函数描述 1 addBuff(...) 给对象附加效果 2 removeBuff(...) 给对象移除指定效果 3 clearAllBuff(...) 给对象清除所有效果 4 clearAllBadBu…...

Java中Stream流的详细使用介绍

Java中Stream流的详细使用介绍 **1. 创建 Stream**从集合创建从数组创建使用 Stream.of 创建创建无限流 **2. 中间操作**过滤&#xff1a;filter映射&#xff1a;map去重&#xff1a;distinct排序&#xff1a;sorted截取&#xff1a;limit 和 skip **3. 终端操作**收集&#xf…...

【重构小程序】升级JDK1.8、SpringBoot2.x 到JDK17、Springboot 3.x(一)

前言 最近想着把大火的deepseek 迁移到小程序里&#xff0c;基于刷题小程序的数据库做一个RAG应用&#xff0c;来进一步扩展答案解析&#xff0c;帮助用户解答相关问题。但是由于之前做的项目都要老了&#xff0c;并不支持spring 的AI模块&#xff0c;因此&#xff0c;我打算先…...

功能丰富的自动化任务软件zTasker_2.1.0_绿色版_屏蔽强制更新闪退

&#x1f680; zTasker 一键式效率倍增器使用指南 &#x1f64f; 致谢 首先感谢开发者提供如此高效的工具&#xff01; 软件本身功能强大&#xff0c;但部分机制需特别注意&#xff01; &#x1f4d6; 软件概述 zTasker 是一款通过自动化脚本/任务流实现效率飞跃的生产力工…...

_ 为什么在python中可以当变量名

在 Python 中&#xff0c;_&#xff08;下划线&#xff09;是一个有效的变量名&#xff0c;这主要源于 Python 的命名规则和一些特殊的使用场景。以下是为什么 _ 可以作为变量名的原因和常见用途&#xff1a; --- ### 1. **Python 的命名规则** Python 允许使用字母&#xff…...

Java 9 到 Java 21 新特性全解析:从语法简化到API增强

一、新特性的概述 纵观Java这几年的版本变化&#xff0c;在Java被收入Oracle之后&#xff0c;Java以小步快跑的迭代方式&#xff0c;在功能更新上迈出了更加轻快的步伐。基于时间发布的版本&#xff0c;可以让Java研发团队及时获得开发人员的反馈&#xff0c;因此可以看到最近…...

LeeCode题库第三十九题

39.组合总和 项目场景&#xff1a; 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同…...

卫星网络仿真平台:IPLOOK赋能空天地一体化通信新生态​

卫星仿真平台 在6G技术加速演进与天地一体化网络建设的大背景下&#xff0c;卫星通信作为地面网络的重要补充&#xff0c;正成为全球通信覆盖的关键支撑。IPLOOK凭借其深厚的技术积累与创新实践&#xff0c;推出的卫星网络仿真平台​&#xff08;SCEPS&#xff09;&#xff0c…...

(十一)基于vue3+mapbox-GL实现模拟高德实时导航轨迹播放

要在 Vue 3 项目中结合 Mapbox GL 实现类似高德地图的实时导航轨迹功能,您可以按照以下步骤进行: 安装依赖: 首先,安装 mapbox-gl 和 @turf/turf 这两个必要的库: npm install mapbox-gl @turf/turf引入 Mapbox GL: 在组件中引入 mapbox-gl 并初始化地图实例: <templ…...

计算机面试项目经历描述技巧

在计算机类岗位的面试中&#xff0c;项目经历是面试官评估候选人技术能力、问题解决能力和实战经验的核心环节。以下是专业化的项目经历描述策略&#xff08;附模板框架&#xff09;&#xff1a; 一、结构化表达框架&#xff08;STAR-RT模型&#xff09; Situation&#xff08;…...

132. 分割回文串 II

简单分析 输入的参数是字符串s&#xff0c;返回值是最小的切割次数。那这个问题的典型解法应该是动态规划&#xff0c;因为我们需要找最优解&#xff0c;而每一步的选择可能会影响后面的结果&#xff0c;但可以通过子问题的最优解来构建整体最优解。 那么动态规划的状态如何定…...

【每日学点HarmonyOS Next知识】全局调整字体、h5选择框无法取消选中、margin不生效、Length转换为具体值、Prop和link比较

【每日学点HarmnoyOS Next知识】全局调整字体、h5选择框无法取消选中、margin不生效、Length转换为具体值、Prop和link比较 1、HarmonyOS 是否存在统一调整全局字体大小的方法&#xff1f; 是否存在统一调整全局字体大小的方法 可以用动态属性&#xff0c;自定义class实现At…...

九、Spring Boot:自动配置原理

深入解析 Spring Boot 自动配置原理 Spring Boot 的自动配置机制是其最核心的特性之一&#xff0c;它极大地简化了 Spring 应用的初始搭建和开发过程。通过自动配置&#xff0c;Spring Boot 能够根据项目的依赖和配置自动加载和配置 Spring 应用的各个部分。本文将深入探讨 Sp…...

(动态规划 最长重复子数组)leetcode 718

思路就是建立一个二维的dp数组&#xff0c;只要nums1[i]nums2[j]&#xff08;nums1和nums2出现重复元素就置1 并加上左上角的值) 为什么代码是nums1 i-1和nums2 i-1 答&#xff1a;因为i和j以1为初始值开始遍历的 为什么要这么做并且为什么要加dp【i-1】【j-1】&#xff1f; …...

SFP+(Enhanced Small Form-factor Pluggable)详解

1. SFP的定义 SFP&#xff08;Small Form-factor Pluggable Plus&#xff09;是SFP的增强版本&#xff0c;专为10Gbps及以上高速网络设计。它继承了SFP的小型化、热插拔特性&#xff0c;但通过优化电气接口和协议支持&#xff0c;实现了更高的传输速率&#xff08;典型为10Gbp…...

计算机毕业设计Hadoop+Spark+DeepSeek-R1大模型音乐推荐系统 音乐数据分析 音乐可视化 音乐爬虫 知识图谱 大数据毕业设计

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…...

Deepseek对ChatGPT的冲击?

从测试工程师的视角来看&#xff0c;DeepSeek对ChatGPT的冲击主要体现在**测试场景的垂直化需求与通用模型局限性之间的博弈**。以下从技术适配性、效率优化、风险控制及未来趋势四个维度展开分析&#xff1a; --- ### **一、技术适配性&#xff1a;垂直领域能力决定工具选择…...

【Python 初级函数详解】—— 参数沙漠与作用域丛林的求生指南

欢迎来到ZyyOvO的博客✨&#xff0c;一个关于探索技术的角落&#xff0c;记录学习的点滴&#x1f4d6;&#xff0c;分享实用的技巧&#x1f6e0;️&#xff0c;偶尔还有一些奇思妙想&#x1f4a1; 本文由ZyyOvO原创✍️&#xff0c;感谢支持❤️&#xff01;请尊重原创&#x1…...

极客大学 java 进阶训练营怎么样,图文详解

Spring 思维导图 Spring 源码学习笔记 有关微服务的面试题&#xff1a; Dubbo中zookeeper做注册中心&#xff0c;如果注册中心集群都挂掉&#xff0c;发布者和订阅者之间还能通信么&#xff1f;微服务学习笔记 有关分布式的面试题&#xff1a; 消息幂等:如何保证消息不被重复…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

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

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