子集和全排列(深度优先遍历)问题
欢迎访问杀马特主页:小小杀马特主页呀!
目录
前言:
例题一·全排列:
1.题目介绍:
2.思路汇总:
3.代码解答:
例题二·子集:
题目叙述:
解法一:
1.思路汇总:
2.代码解答:
解法二:
1.思路汇总:
2.代码解答:
文末小总结:
前言:
本篇采用两道例题来讲解利用枚举元素的方法使用决策树通过递归以及穿插回溯来解答类似此类问题的系列模版操作(涉及全局变量以及引用传参使用需要回溯问题与具体什么时候使用等)。
当我们使用全局变量大都就要手动的回溯了,因为它回归到上一层自己不会改变,这里既可以选择全局变量又可以选择引用传参,但是比如一个递归函数需要使用多个变量,这时候引用传参就麻烦了,故需要我们使用全局变量了,因此视情况而定(本篇我们都使用的是全局变量)。
例题一·全排列:
1.题目介绍:

欢迎大家来挑战:leetcode原题链接: . - 力扣(LeetCode)
2.思路汇总:
画出决策树,然后令dfs函数能帮我们完成此元素位置(从其上到末的path都放入ret)然后对于这个数组就是要遍历它了,由于我们要定义的path是全局遍历故
要考虑回溯(复原操作):这里就是我们每次往后递归,不能出现前面的元素,故这里开一个bool类型数组记录一下
(一开始是false,变成true就是已经出现了,故不进行操作继续循环)
终止条件:当path满了(等于nums的size)就返回就行了。
思路:从下标0开始遍历数组,遍历到一个就放入path,记录状态,然后继续下面递归,依次重复,
最后肯定会path等于size然后就放入ret,然后回溯:在上一层完成删除path的back即恢复现场的操作,每一次完成一条路线就往回溯,最后归到第一次for循环到退出。
决策图解:

3.代码解答:
class Solution {
public:vector<vector<int>> ret;vector<int> path;bool check[7]={false};//如果换成vector的bool类型只能用原数组指针区间初始化void dfs(vector<int>& nums){if(path.size()==nums.size()){ret.push_back(path);//终止条件return;}for(int i=0;i<nums.size();i++){if(check[i]==false){//使用后该状态防止重复使用path.push_back(nums[i]);check[i]=true;dfs(nums);//回溯(恢复现场):path.pop_back();check[i]=false;}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}};
例题二·子集:
本题采取两种解法解答,一种是叶子节点放入ret,另一种就是每当递归到一层,这一层的path就是要存入ret的结果。
题目叙述:

欢迎大家来挑战:leetcode原题链接:. - 力扣(LeetCode)
解法一:
1.思路汇总:
思路:枚举元素:分为选i位置的数和不选两条路径,然后往下递归,最后决策树相当于叶子节点的数就是我们要推进ret的,这里可以假设dfs递归函数可以帮我们完成从传入
的pos位置一直走到叶子位置的所有分支路径最后的到叶子节点的path都放入ret,然后在第一次分别传入它的左支和右支就可以了。
细节:注意传入的pos的位置以及回溯的时候path的变化

2.代码解答:
class Solution {
public:vector<vector<int>> ret;vector<int> path;
void dfs(vector<int>& nums,int pos){if(pos==nums.size()){ret.push_back(path);path.pop_back();//回溯return;}//可分为左支不走,右支走://走pos位置的元素(右支):path.push_back(nums[pos]);dfs(nums,pos+1);//不走pos位置的元素(左支):dfs(nums,pos+1);}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}
解法二:
1.思路汇总:
思路:我们遍历数组放入path,并且当递归到下一层遍历的时候就是当前位置的下一个开始,所以循环的第一个是pos位置,结合每次下一层递归结束回到上一层都会把下一层的
path里面加入的nums[i]删除即回溯,保证了每次每当我们进入一次递归第一个就是子集。
细节:1·为什么ret添加不在for里面:这样的话最后一次递归完成后无法添加最后一次的结果。
2·为什么每次递归函数传参是i+1不是pos+1呢:这样的话就会导致递归回来的时候走for里的i++的时候再次传入pos+1,又会进行刚才的递归操作了,不符合预期。

2.代码解答:
void dfs(vector<int>& nums,int pos){ret.push_back(path);for(int i=pos;i<nums.size();i++){path.push_back(nums[i]);dfs(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}
文末小总结:
像这种类型的dfs思路就是首先根据题意采取穷举等方法画出决策树,然后根据规则转化成递归代码:终止条件,递归操作,回溯,剪枝的判断,其次就是合理应用全局变量等
相关文章:
子集和全排列(深度优先遍历)问题
欢迎访问杀马特主页:小小杀马特主页呀! 目录 前言: 例题一全排列: 1.题目介绍: 2.思路汇总: 3.代码解答: 例题二子集: 题目叙述: 解法一: 1.思路汇总…...
判断检测框是否在感兴趣区域(ROI)内
判断检测框是否在感兴趣区域(ROI)内 在计算机视觉和图像处理中,我们经常需要确定一个矩形检测框是否位于一个特定的感兴趣区域(Region of Interest, ROI)内。这个ROI可以是一个多边形,而检测框则是一个矩形…...
正点原子阿尔法ARM开发板-IMX6ULL(九)——关于SecureCRT连接板子上的ubuntu
文章目录 一、拨码器二、SecureCRT 一、拨码器 emmm,也是好久没学IMX6ULL了,也是忘了拨码器决定了主板的启动方式 一种是直接从TF卡中读取文件(注意这里是通过imdownload软件编译好了之后,通过指令放入TF卡) 一种是现在这种用串口…...
微信支付Java+uniapp微信小程序
JS: request.post(/vip/pay, {//这是自己写的java支付接口id: this.vipInfo.id,payWay: wechat-mini}).then((res) > {let success (res2) > {//前端的支付成功回调函数this.$refs.popup.close();// 支付成功刷新当前页面setTimeout(() > {this.doGetVipI…...
【NOIP提高组】加分二叉树
【NOIP提高组】加分二叉树 💐The Begin💐点点关注,收藏不迷路💐 设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整…...
HarmonyOS 相对布局(RelativeContainer)
1. HarmonyOS 相对布局(RelativeContainer) 文档中心:https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V5/arkts-layout-development-relative-layout-V5 RelativeContainer为采用相对布局的容器,支持容器内部的子元素设…...
webpack5搭建react脚手架详细步骤
1. 初始化项目 首先,创建一个新目录并初始化项目: bash mkdir create-react cd create-react pnpm init --y git init 这里使用pnpm作为包管理工具,因为它在处理依赖和速度上表现更好。 2. 安装React和TypeScript 安装React和React-DOM…...
速盾:高防cdn怎么拦截恶意ip?
高防CDN(Content Delivery Network)是一种用于防御网络攻击和提供高可用性的服务。它通过分发网络流量,将用户的请求导向最近的服务器,从而提高网站的加载速度和稳定性。然而,不可避免地,有些恶意IP地址会试…...
太阳能面板分割系统:训练自动化
太阳能面板分割系统源码&数据集分享 [yolov8-seg-EfficientHead&yolov8-seg-vanillanet等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI Globa…...
C++笔记---位图
1. 位图的概念 位图(Bitmap)是一种基于位操作的数据结构,用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组,每个元素对应一个二进制位,若该元素存在,则对应的位为1;若不存在ÿ…...
ABC370
## A - Raise Both Hands (模拟) 题意:输入l,r,如果l1r0输出yes,l0r1输出no,否则输出Invalid 代码: #include<bits/stdc.h> using namespace std; typedef long long ll; vo…...
C语言[求x的y次方]
C语言——求x的y次方 这段 C 代码的目的是从用户输入获取两个整数 x 和 y ,然后计算 x 的 y 次幂(不过这里有个小错误,实际计算的是 x 的 (y - 1) 次幂,后面会详细说),最后输出结果。 代码如下: #include…...
JavaScript part2
一.前言 前面我们讲了一下js的基础语法,但是这些还是远远不够的,我们要想操作标签,实现一个动态且好看的页面,就得学会BOM和DOM,这些都是浏览器和页面的,这样我们才能实现一个好看的页面 二.BOM对象 BOM…...
HarmonyOS开发 - 本地持久化之实现LocalStorage实例
用户首选项为应用提供Key-Value键值型的数据处理能力,支持应用持久化轻量级数据,并对其修改和查询。数据存储形式为键值对,键的类型为字符串型,值的存储数据类型包括数字型、字符型、布尔型以及这3种类型的数组类型。 说明&#x…...
【C++打怪之路Lv12】-- 模板进阶
#1024程序员节|征文# 🌈 个人主页:白子寰 🔥 分类专栏:重生之我在学Linux,C打怪之路,python从入门到精通,数据结构,C语言,C语言题集👈 希望得到您…...
第23周Java主流框架入门-SpringMVC 2.RESTful开发风格
课程笔记:RESTful 开发风格 课程介绍 本节课程介绍 RESTful 开发风格,以及如何在 Spring MVC 中应用这种开发模式。传统 MVC 开发通过 Servlet、JSP 和 Java Bean 实现前后端交互,而 RESTful 开发提供了一种新的理念,更适合现代…...
QT枚举类型转字符串和使用QDebug<<重载输出私有枚举类型
一 将QT自带的枚举类型转换为QString 需要的头文件: #include <QMetaObject> #include <QMetaEnum> 测试代码 const QMetaObject *metaObject &QImage::staticMetaObject;QMetaEnum metaEnum metaObject->enumerator(metaObject->indexOf…...
手机柔性屏全贴合视觉应用
在高科技日新月异的今天,手机柔性显示屏作为智能手机市场的新宠,以其独特的可弯曲、轻薄及高耐用性特性引领着行业潮流。然而,在利用贴合机加工这些先进显示屏的过程中,仍面临着诸多技术挑战。其中,高精度对位、应力控…...
《Python游戏编程入门》注-第3章3
《Python游戏编程入门》的“3.2.4 Mad Lib”中介绍了一个名为“Mad Lib”游戏的编写方法。 1 游戏玩法 “Mad Lib”游戏由玩家根据提示输入一些信息,例如男人姓名、女人姓名、喜欢的食物以及太空船的名字等。游戏根据玩家输入的信息编写出一个故事,如图…...
Netty-TCP服务端粘包、拆包问题(两种格式)
前言 最近公司搞了个小业务,需要使用TCP协议,我这边负责服务端。客户端是某个设备,客户端传参格式、包头包尾等都是固定的,不可改变,而且还有个蓝牙传感器,透传数据到这个设备,然后通过这个设备…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
鸿蒙HarmonyOS 5军旗小游戏实现指南
1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发,采用DevEco Studio实现,包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
python基础语法Ⅰ
python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器,来进行一些算术…...
Easy Excel
Easy Excel 一、依赖引入二、基本使用1. 定义实体类(导入/导出共用)2. 写 Excel3. 读 Excel 三、常用注解说明(完整列表)四、进阶:自定义转换器(Converter) 其它自定义转换器没生效 Easy Excel在…...
spring boot使用HttpServletResponse实现sse后端流式输出消息
1.以前只是看过SSE的相关文章,没有具体实践,这次接入AI大模型使用到了流式输出,涉及到给前端流式返回,所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...
Java设计模式:责任链模式
一、什么是责任链模式? 责任链模式(Chain of Responsibility Pattern) 是一种 行为型设计模式,它通过将请求沿着一条处理链传递,直到某个对象处理它为止。这种模式的核心思想是 解耦请求的发送者和接收者,…...

