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

回溯算法|78.子集

力扣题目链接

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集,要放在终止添加的上面,否则会漏掉自己if (startIndex >= nums.size()) { // 终止条件可以不加return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

这题比较好理解啦~

思路

求子集问题和77.组合 (opens new window)和131.分割回文串 (opens new window)又不一样了。

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点!

其实子集也是一种组合问题,因为它的集合是无序的,子集{1,2} 和 子集{2,1}是一样的。

那么既然是无序,取过的元素不会重复取,写回溯算法的时候,for就要从startIndex开始,而不是从0开始!

有同学问了,什么时候for可以从0开始呢?

求排列问题的时候,就要从0开始,因为集合是有序的,{1, 2} 和{2, 1}是两个集合,排列问题我们后续的文章就会讲到的。

以示例中nums = [1,2,3]为例把求子集抽象为树型结构,如下:

78.子集

从图中红线部分,可以看出遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合

#回溯三部曲

  • 递归函数参数

全局变量数组path为子集收集元素,二维数组result存放子集组合。(也可以放到递归函数参数里)

递归函数参数在上面讲到了,需要startIndex。

代码如下:

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {

递归终止条件

从图中可以看出:

78.子集

剩余集合为空的时候,就是叶子节点。

那么什么时候剩余集合为空呢?

就是startIndex已经大于数组的长度了,就终止了,因为没有元素可取了,代码如下:

if (startIndex >= nums.size()) {return;
}

其实可以不需要加终止条件,因为startIndex >= nums.size(),本层for循环本来也结束了

  • 单层搜索逻辑

求取子集问题,不需要任何剪枝!因为子集就是要遍历整棵树

那么单层递归逻辑代码如下:

for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);    // 子集收集元素backtracking(nums, i + 1);  // 注意从i+1开始,元素不重复取path.pop_back();            // 回溯
}

根据关于回溯算法,你该了解这些! (opens new window)给出的回溯算法模板:

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}

自己的思路: 

其实我不太清楚空集它是如何保存的。

result.push_back(path); // 收集子集,要放在终止添加的上面,否则会漏掉自己

是这个吗?好像不是

好像也是的,一开始没有路径,直接push进去的就是空集

后面的就和之前几天写的代码差不多了,好理解~

 

相关文章:

回溯算法|78.子集

力扣题目链接 class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集&#xff0c;要放在终止添加的上面&#xff0c;否则会漏掉自…...

VC++、GCC、CLANG,INT128有符号整数编译器关键字

注意INT128为目标平台扩展关键字&#xff0c;不属于C/C语言本身支持特性&#xff0c;每个C/C编译器平台支持上都略有不同&#xff0c;甚至不支持。 可以详细参考本人此篇文章&#xff1a; GUN C/C (GCC/CLANG) 对于 __int128_t &#xff08;128位有符号大整数的扩展支持平台限…...

用于HUD平视显示器的控制芯片:S2D13V40

一款利用汽车抬头显示技术用于HUD平视显示器的控制芯片:S2D13V40。HUD的全称是Head Up Display&#xff0c;即平视显示器&#xff0c;以前应用于军用飞机上&#xff0c;旨在降低飞行员需要低头查看仪表的频率。起初&#xff0c;HUD通过光学原理&#xff0c;将驾驶相关的信息投射…...

JSP使用模板字符串数据不能渲染的问题

entrap father 的 rubbish JSP 数据不能直接渲染,要从接口请求后去拼接结构 然后模板字符串不能直接用 用以下方法是不能渲染出数据的 let div <div class"circulation"><div class"list"><div class"left"><div class&qu…...

AI音乐GPT时刻来临:Suno 快速入门手册!

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…...

数字乡村发展蓝图:科技赋能农村实现全面振兴

目录 一、数字乡村发展蓝图的内涵与目标 二、科技赋能农村&#xff1a;数字乡村发展的动力与路径 &#xff08;一&#xff09;加强农业科技创新&#xff0c;提升农业生产效率 &#xff08;二&#xff09;推进农村电商发展&#xff0c;拓宽农民增收渠道 &#xff08;三&…...

Day42 动态规划 part04

Day42 动态规划 part04 46. 携带研究材料(卡哥的卡码网的题目) 背包问题 我的思路: 写不了一点儿…T^T 总结规律就是&#xff0c;dp数组要比原来各个size 1&#xff0c;dp[i][j] Math.max(xxx, xxxx&#xff08;根据题目情况进行各种处理&#xff09;) 解答&#xff1a; …...

python set是什么类型

python set是一种数据类型&#xff0c;数学里的集合概念&#xff0c;在Python语言里对应的是set类型。与list&#xff0c;tuple不同的地方是&#xff0c;set更加强调的是一种“从属关系”&#xff08;membership&#xff09;&#xff0c;跟顺序无关&#xff0c;所以有重复的元素…...

redis事务(redis features)

redis支持事务&#xff0c;也就是可以在一次请求中执行多个命令。redis中的事务主要是通过MULTI和EXEC这两个命令来实现的。 MULTI命令用来开启一个事务&#xff0c;事务开启之后&#xff0c;所有的命令就都会被放入到一个队列中&#xff0c;最后通过一个EXEC命令来执行事务中…...

SpringBoot整合minio

SpringBoot整合minio 1. 下载及安装1.1 windows版本1.2 Linux版本 2. SpringBoot整合minio2.1 依赖2.2 配置文件2.3 配置类2.4 工具类2.5 测试1. 业务层2. 控制层 1. 下载及安装 1.1 windows版本 目录结构 启动文件 标红的地方按实际安装地更改 echo off REM 声明采用UT…...

3090. 每个字符最多出现两次的最长子字符串

说在前面 &#x1f388;不知道大家对于算法的学习是一个怎样的心态呢&#xff1f;为了面试还是因为兴趣&#xff1f;不管是出于什么原因&#xff0c;算法学习需要持续保持。 题目描述 给你一个字符串 s &#xff0c;请找出满足每个字符最多出现两次的最长子字符串&#xff0c;…...

26.活锁、饥饿锁

两个线程&#xff0c;相互改变了对方结束条件&#xff0c;导致两个线程不能结束。执行时间也都是一样&#xff0c;导致两个线程永远不会结束。 Slf4j public class LiveLockDemo {static volatile int count 10;public static void main(String[] args) {new Thread(() ->…...

docker 安装nginx

一、先查看有没有nginx镜像 docker images 二、发现没有nginx镜像&#xff0c;下载最新镜像 docker pull nginx 三、运行镜像 为了先复制出部分文件&#xff0c;先启动一个临时容器 docker run --name nginx -p 9001:80 -d nginx docker cp nginx:/etc/nginx/conf.d /home/…...

2024年阿里云新用户便宜购买云服务器攻略:5大细节助你降低购买成本

随着互联网的蓬勃发展&#xff0c;无论是个人还是企业&#xff0c;拥有一个稳定且高效的网站或APP已成为提升竞争力的关键。为了将这些项目部署并运行起来&#xff0c;购买一台实用又便宜的云服务器是必不可少的。阿里云作为国内首屈一指的云服务提供商&#xff0c;自然成为了众…...

SSTI模板注入(jinja2)

前面学习了SSTI中的smarty类型&#xff0c;今天学习了Jinja2&#xff0c;两种类型都是flask框架的&#xff0c;但是在注入的语法上还是有不同 SSTI&#xff1a;服务器端模板注入&#xff0c;也属于一种注入类型。与sql注入类似&#xff0c;也是通过凭借进行命令的执行&#xff…...

ESP32学习---ESP-NOW(一)

ESP32学习---ESP-NOW&#xff08;一&#xff09; 官网简介arduino 官网简介 首先看官网的介绍&#xff1a;https://www.espressif.com.cn/zh-hans/solutions/low-power-solutions/esp-now ESP-NOW 是乐鑫定义的一种无线通信协议&#xff0c;能够在无路由器的情况下直接、快速…...

C++核心高级编程 --- 3、函数提高

文章目录 第三章&#xff1a;3.函数提高3.1 函数默认参数3.2 函数占位参数3.3 函数重载3.3.1 函数重载概述3.3.2 注意事项 第三章&#xff1a; 3.函数提高 3.1 函数默认参数 语法结构&#xff1a;返回值类型 函数名 (参数 默认值){} #include <iostream> using name…...

【微服务篇】深入理解分布式消息队列系统

分布式消息队列是一种在多个服务器、应用或服务之间进行消息传递的技术。它使得各个独立的组件可以通过异步消息进行通信&#xff0c;提高了系统的可扩展性、解耦性和可靠性。 典型应用场景 1. 异步处理 在许多系统中&#xff0c;某些任务的处理可能需要较长时间&#xff0c…...

基于k8s的web服务器构建

文章目录 k8s综合项目1、项目规划图2、项目描述3、项目环境4、前期准备4.1、环境准备4.2、ip划分4.3、静态配置ip地址4.4、修改主机名4.5、部署k8s集群4.5.1、关闭防火墙和selinux4.5.2、升级系统4.5.3、每台主机都配置hosts文件&#xff0c;相互之间通过主机名互相访问4.5.4、…...

【名词解释】ImageCaption任务中的CIDEr、n-gram、TF-IDF、BLEU、METEOR、ROUGE 分别是什么?它们是怎样计算的?

CIDEr CIDEr&#xff08;Consensus-based Image Description Evaluation&#xff09;是一种用于自动评估图像描述&#xff08;image captioning&#xff09;任务性能的指标。它主要通过计算生成的描述与一组参考描述之间的相似性来评估图像描述的质量。CIDEr的独特之处在于它考…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...

相关类相关的可视化图像总结

目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系&#xff0c;可直观判断线性相关、非线性相关或无相关关系&#xff0c;点的分布密…...

React核心概念:State是什么?如何用useState管理组件自己的数据?

系列回顾&#xff1a; 在上一篇《React入门第一步》中&#xff0c;我们已经成功创建并运行了第一个React项目。我们学会了用Vite初始化项目&#xff0c;并修改了App.jsx组件&#xff0c;让页面显示出我们想要的文字。但是&#xff0c;那个页面是“死”的&#xff0c;它只是静态…...