当前位置: 首页 > 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的独特之处在于它考…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

【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…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...