Day65 代码随想录打卡|回溯算法篇---组合总和II

题目(leecode T40):

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

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

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

方法:本题的要求是每个元素在组合中只能出现一次,并且候选的数字是有可能重复的,因此需要去重操作。分析回溯三部曲。

1:传入参数与返回值:与组合总和的套路相同,此题还需要加一个bool型数组used,用来记录同一树枝上的元素是否使用过。这个集合去重的重任就是used来完成的。

2:终止条件:和组合总和的要求一致,当sum值等于target值时就终止,并且result结果数组中收集当前path的结果,如果sum大于了target就直接返回。

3:单层处理逻辑:本题有一个难点就是因为元素有重复所以最终的结果中我们要去重,有一种方法是算出所有的结果然后再利用set或map的结构去重,但这种方法容易超时,因此我们在计算结果的过程中就需要去重了。去重具体使用的时一个bool类型的used数组,他记录着候选数组中的每个元素的值是否使用过了。具体逻辑入代码所示、

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {// used[i - 1] == true,说明同一树枝candidates[i - 1]使用过// used[i - 1] == false,说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum += candidates[i];path.push_back(candidates[i]);used[i] = true;backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1,这里是i+1,每个数字在每个组合中只能使用一次used[i] = false;sum -= candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序,让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3223982.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

JAVA的String的不可变特性

在学习JAVA的时候&#xff0c;看到了JAVA的String具有不可变的特性&#xff0c;他是说&#xff0c;JAVA的String在创建好后&#xff0c;JVM将这个String变量指向内存中的一个地址&#xff0c;当下次改变这个String变量的时候&#xff0c;改变的不是这个变量的值&#xff0c;而是…

可转债之强赎条款

摘要&#xff1a;每天学习一点金融小知识 做可转债投资&#xff0c;强赎风险是特别需要注意的&#xff0c;若投资者没有及时采取措施&#xff0c;就有可能造成很大的损失。本文从可转债的定义、强赎条款的原因及强赎的情况几个方面来介绍下可转债的强赎条款。 什么是可转换债券…

如何评价Flutter?

哈喽&#xff0c;我是老刘 我们团队使用Flutter已经快6年了。 有很多人问过我们对Flutter的评价。 今天在这里回顾一下6年前选择Flutter时的原因&#xff0c;以及Flutter在这几年中的实际表现如何。 选择Flutter时的判断 1、性能 最开始吸引我们的就是其优秀的性能。 特别是…

imx6ull/linux应用编程学习(15) 移植MQTT客户端库

1. 准备开发环境 确保你的Ubuntu系统已经安装了必要的工具和依赖项。打开终端并运行以下命令&#xff1a; sudo apt update sudo apt install build-essential cmake git2. 获取MQTT库 git clone https://github.com/eclipse/paho.mqtt.c.git cd paho.mqtt.c3. 编译MQTT库 mk…

FullCalendar的使用,react日历组件

1.下载 yarn add fullcalendar/core fullcalendar/react fullcalendar/daygrid 2.运行 import React from react; import FullCalendar from "fullcalendar/react"; import dayGridPlugin from "fullcalendar/daygrid";const ExperimentalSchedule () …

昇思25天学习打卡营第10天|应用实践之基于MindNLP和ChatGLM-6B实现一个聊天应用

基本介绍 今天的应用实践是基于MindSpore和ChatGLM-6B实现一个&#xff08;伪&#xff09;聊天应用&#xff0c;本质上就是使用MindSpore下载模型及其权重&#xff0c;然后调用相关API输入自己想说的话&#xff0c;就可以得到回复&#xff0c;如果要打造真正的聊天应用&#xf…

中文大模型基准测评2024上半年报告

中文大模型基准测评2024上半年报告 原创 SuperCLUE CLUE中文语言理解测评基准 2024年07月09日 18:09 浙江 SuperCLUE团队 2024/07 背景 自2023年以来&#xff0c;AI大模型在全球范围内掀起了有史以来规模最大的人工智能浪潮。进入2024年&#xff0c;全球大模型竞争态势日益加…

对比学习和多模态任务

1. 对比学习 对比学习&#xff08;Contrastive Learning&#xff09;是一种自监督学习的方法&#xff0c;旨在通过比较数据表示空间中的不同样本来学习有用的特征表示。其核心思想是通过最大化同类样本之间的相似性&#xff08;或降低它们之间的距离&#xff09;&#xff0c;同…

科普文本分类背后的数学原理——最新版《数学之美》第14、15章读书笔记

新闻分类&#xff0c;或广义上的文本分类&#xff0c;其核心任务是根据文本内容将相似文本聚合在同一类别中。在新闻领域&#xff0c;这意味着将报道划分为财经、体育、军事等不同主题。人类执行此任务时&#xff0c;通过阅读和理解新闻的主旨来进行归类。然而&#xff0c;作者…

第二章 基础知识(4) - 日志记录

在默认日志级别&#xff0c;Blazor项目中默认提供如下日志记录提供程序&#xff1a; 在服务器上&#xff08;Blazor Server&#xff09;&#xff0c;日志记录仅发生在 LogLevel.Information 或更高级别的 Development 环境中的服务器端 .NET 控制台。 在客户端上&#xff08;B…

泛微E9开发 控制日期浏览按钮的可选日期范围

控制日期浏览按钮的可选日期范围 1、需求说明2、实现方法3、扩展知识点控制日期浏览按钮的可选日期范围格式参数说明演示 1、需求说明 控制日期浏览按钮的可选日期范围为2024/07/01~2024/07/31&#xff0c;如下图所示 2. 控制日期浏览按钮的可选日期范围在当前时间的前一周~当…

生成多个ssh访问不同git

如果&#xff0c;你的git代码仓库&#xff0c;比如说腾讯云coding&#xff0c;通过ssh秘钥访问&#xff0c;一直用的好好的&#xff0c;有一天&#xff0c;你又增加一个aliyun云效的代码仓库&#xff0c;又配置了aliyun云效的秘钥并且&#xff0c;根据aliyun云效的官方文档上传…

Django 更新数据 save()方法

1&#xff0c;添加模型 Test/app11/models.py from django.db import modelsclass Post(models.Model):title models.CharField(max_length200)content models.TextField()pub_date models.DateTimeField(date published)class Book(models.Model):title models.CharFie…

【Linux】多线程_2

文章目录 九、多线程2. 线程的控制 未完待续 九、多线程 2. 线程的控制 主线程退出 等同于 进程退出 等同于 所有线程都退出。为了避免主线程退出&#xff0c;但是新线程并没有执行完自己的任务的问题&#xff0c;主线程同样要跟进程一样等待新线程返回。 pthread_join 函数…

力扣喜刷刷--day1

1.无重复字符的最长子串 知识点&#xff1a;滑动窗口 基本概念 窗口&#xff1a;窗口是一个连续的子序列&#xff0c;可以是固定长度或可变长度。滑动&#xff1a;窗口在数据序列上移动&#xff0c;可以是向左或向右。边界&#xff1a;窗口的起始和结束位置。 应用场景 字符…

基于Python的51job招聘数据采集与可视化项目实践

项目背景与目标 在当今竞争激烈的就业市场中&#xff0c;深入分析招聘信息对于求职者和企业都具有重要意义。基于Python的51job招聘数据采集与可视化项目旨在通过自动化手段高效获取大量招聘信息&#xff0c;并对这些数据进行深度分析和展示。 51job作为中国领先的招聘网站&…

干货:高水平论文写作思路与方法

前言:Hello大家好,我是小哥谈。高水平论文的写作需要扎实的研究基础和严谨的思维方式。同时,良好的写作技巧和时间管理也是成功的关键。本篇文章转载自行业领域专家所写的一篇文章,希望大家阅读后可以能够有所收获。🌈 目录 🚀1.依托事实/证据,通过合理的逻辑,…

【深度学习基础】环境搭建 linux系统下安装pytorch

目录 一、anaconda 安装二、创建pytorch1. 创建pytorch环境&#xff1a;2. 激活环境3. 下载安装pytorch包4. 检查是否安装成功 一、anaconda 安装 具体的安装说明可以参考我的另外一篇文章【环境搭建】Linux报错bash: conda: command not found… 二、创建pytorch 1. 创建py…

C++ 是否变得比 C 更流行了?

每年都会出现一种新的编程语言。创造一种新语言来解决计算机科学中的挑战的诱惑很难抗拒。一些资料表明&#xff0c;目前有多达 2,500 种语言&#xff0c;这并不奇怪&#xff01; 对于我们嵌入式软件开发人员来说&#xff0c;这个列表并不长。事实上&#xff0c;我们可以用一只…

【Java算法】二分查找 下

&#x1f525;个人主页&#xff1a; 中草药 &#x1f525;专栏&#xff1a;【算法工作坊】算法实战揭秘 一.山脉数组的峰顶索引 题目链接&#xff1a;852.山脉数组的峰顶 ​ 算法原理 这段代码实现了一个查找山峰数组中峰值索引的算法。山峰数组是一个先递增后递减的数组&…