递归实现指数型枚举(acwing)

题目描述:

从 1∼n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。

输入格式:

输入一个整数 n。

输出格式:

每行输出一种方案。

同一行内的数必须升序排列,相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案,输出空行。

本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。

数据范围:

1≤n≤15;

输入样例:

3

输出样例:


3
2
2 3
1
1 3
1 2
1 2 3

分析步骤:

  第一:理清思路:

  1. 我们这道题还是DFS去求解,但是这道题目要我们求解的是指数型枚举,所以和组合型,排列型不一样。大家要明白组合和排列和指数型的区别。我们求解DFS有两种方法,一种是枚举位置一种是枚举数字本题采用枚举位置的方法,因为这个更简单跟容易理解。

  2. 枚举位置,我们先枚举第一个位置他有四种选择不选,1,2,3这样我们就可以像一颗树一样去画出来。如果选了就标记一下这个数已经选过了如果不选则放弃这个数再向后去寻找是否选择其他的数。这样我们每次都有两个选择,慢慢向下去搜索我们会发现这是一颗递归搜索树。大家可以动手画一画,看看是否和我一样。

  第二:书写主函数,构建整体框架:

  1.  输入值,进入DFS这个1代表我们已经遍历到了第几个位置。书写DFS我们一定要明白,自己对于变量的定义是什么,只有明白了我们在之后的递归中才不会迷失。

int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

  第三:书写DFS函数

  1. 我们一般先写结束条件如果我们的x>n就代表所有的数都经过了选择,我们就按顺序把那些选过的标记了的输出出来就可以。

  2. 我们先假设他不选就将状态改为false再去向下递归,这样搜索一遍之后返回,再假设选择这个数再去递归,这样就可以保证所有的可能都在这里面了。

void dfs(int x){
     if(x>n){
         for(int i = 1 ; i <= n ; i ++){
             if(st[i]) cout<<i<<" ";
         }
         cout<<endl;
         return ;
     }
    
    st[x] = false;
    dfs(x+1);
    
    st[x] = true;
    dfs(x+1);
}

代码:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;
bool st[N];
int n ;

void dfs(int x){
     if(x>n){
         for(int i = 1 ; i <= n ; i ++){
             if(st[i]) cout<<i<<" ";
         }
         cout<<endl;
         return ;
     }
    
    st[x] = false;
    dfs(x+1);
    
    st[x] = true;
    dfs(x+1);
}

int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

 注意:递归实现排列型枚举;递归实现组合型枚举;递归实现指数型枚举。这三道题目代表了DFS三大标准题型,学会这三道模板题目才有可能继续去学习更难的DFS。

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一周年纪念

文章目录 机缘&#xff1a;命运之门收获---知识之心日常---灵魂之窗成就 — 自我之光憧憬 — 未来之路 机缘&#xff1a;命运之门 “人生是由一连串的选择组成&#xff0c;而真正的成长&#xff0c;往往始于最具挑战性的决定。” —— 这句话恰如其分地概括了我选择跨考计算机的…

自动驾驶执行层 - 线控底盘基础原理(非常详细)

自动驾驶执行层 - 线控底盘基础原理(非常详细) 附赠自动驾驶学习资料和量产经验&#xff1a;链接 1. 前言 1.1 线控的对象 在自动驾驶行业所谓的“感知-定位-决策-执行”的过程中&#xff0c;在末端的执行层&#xff0c;车辆需要自主执行决策层所给出的指令&#xff0c;具体…

2024最全ChatGPT支持GPTs使用教程+Prompt应用预设词教程

使用指南 直接复制使用 可以前往已经添加好Prompt预设的AI系统测试使用&#xff08;可自定义添加使用&#xff09; https://ai.sparkaigf.com 现已支持GPTs 雅思写作考官 我希望你假定自己是雅思写作考官&#xff0c;根据雅思评判标准&#xff0c;按我给你的雅思考题和对应…

【多模态融合】MetaBEV 解决传感器故障 3D检测、BEV分割任务

前言 本文介绍多模态融合中&#xff0c;如何解决传感器故障问题&#xff1b;基于激光雷达和相机&#xff0c;融合为BEV特征&#xff0c;实现3D检测和BEV分割&#xff0c;提高系统容错性和稳定性。 会讲解论文整体思路、模型框架、论文核心点、损失函数、实验与测试效果等。 …

Python 基于列表实现的通讯录管理系统(有完整源码)

目录 通讯录管理系统 PersonInformation类 ContactList类 menu函数 main函数 程序的运行流程 完整代码 运行示例 通讯录管理系统 这是一个基于文本的界面程序&#xff0c;用户可以通过命令行与之交互&#xff0c;它使用了CSV文件来存储和读取联系人信息&#xff0c;这…

浅谈Redis和一些指令

浅浅谈一谈Redis的客户端 Redis客户端 Redis也是一个客户端/服务端结构的程序。 MySQL也是一个客户端/服务端结构的程序。 Redis的客户端也有多种形态 1.自带命令行客户端 redis-cli 2.图形化界面的客户端&#xff08;桌面程序&#xff0c;web程序&#xff09; 像这样的图形…

3d代理模型怎么转换成标准模型---模大狮模型网

在当今的虚拟世界中&#xff0c;3D建模技术被广泛运用于游戏开发、电影制作、工业设计等领域。在3D建模过程中&#xff0c;有时会遇到需要将代理模型转换成标准模型的情况。模大狮将从理论和实践两方面&#xff0c;介绍如何将3D代理模型转换成标准模型&#xff0c;以帮助读者更…

推荐一款免费开源引擎:批量识别PDF及图片表格及文字(可本地化部署)

在数字化时代&#xff0c;信息的快速处理和高效管理成为企业和个人的重要需求。表格文字识别技术作为一项关键的技术&#xff0c;能够将纸质或图片中的表格数据快速转换为结构化的电子数据&#xff0c;极大地提高了数据处理的效率和准确性。本文将对思通数科的表格文字识别技术…

MySQL复制拓扑2

文章目录 主要内容一.配置基本复制结构1.分别在三台主机上停止mysqld服务&#xff0c;并对状态进行确认&#xff1a;代码如下&#xff08;示例&#xff09;: 2.对三个MySQL服务器的配置文件分别进行编辑&#xff0c;在[mysqld] 选项组中添加以下红色条目&#xff1a;3.在数据目…

淘宝优惠券领取软件叫什么?

草柴返利APP是一款淘宝优惠券领取软件。用户可以通过草柴淘宝优惠券领取软件轻松查找领取淘宝大额隐藏优惠券&#xff0c;领取成功后再购物可享受券后价优惠。同时&#xff0c;通过草柴APP领券购买成功&#xff0c;确认收货后再回到草柴APP提取购物返利&#xff0c;享受双重省钱…

【自用笔记】【大数据】

1 mapreduce &#xff08;1&#xff09;Map任务的数量&#xff1a;由输入数据的大小决定的&#xff0c;如文件数量和大小、HDFS块大小以及FileInputFormat的设置等。每个MapSlot可以运行一个Map任务 &#xff08;2&#xff09;Reduce任务的数量&#xff08;分区数&#xff09;&…

DHCP-PXE

Dynamic Host Configuration Protocol 动态主机配置协议 1.Selinux 调试为Permission 防火墙配置 搭建DHCP的主机必须有一个静态地址&#xff0c;提前配置好 安装DHCP软件 服务名为dhcpd DHCP地址分配四次会话&#xff0c; DISCOVERY发现 OFFER 提供 REQUEST 回应 A…

vue使用iview导航栏Menu activeName不生效

activeName不生效 一、问题一、解决方案&#xff0c; 一、问题 根据ivew官网的提示&#xff0c;设置了active-name和open-names以后&#xff0c;发现不管是设置静态是数据还是设置动态的数据&#xff0c;都不生效 一、解决方案&#xff0c; 在设置动态名称的时候&#xff0c…

修复打印机显示为脱机的几种方法,总有一种适合你

打印机显示为脱机有几个可能的原因。在大多数情况下,只要对症下药,问题就很容易解决。下面解释了打印机脱机的原因,以及如何使其联机并再次打印。 “打印机脱机”是什么意思 当打印机显示为脱机时,这意味着它当前未通过电缆或Wi-Fi网络连接到计算机。它无法与你的计算机通…

Feign(黑马程序员)

Feign是代替RestTemplate进行http请求的。 定义和使用 Feign 客户端&#xff1a; 1 引入依赖&#xff1a; <dependency> <groupId>org.springframework.cloud</groupId> <artifactId>spring-cloud-starter-openfeign</artifactId> </depe…

Autosar BswM 模式管理

EcuMs管理ECU上下电状态,BswM管理模式,协同工作。当使用EcuM - Fixed时,它将向BswM指示当前ECU状态 有了BswM,从图可以更加直观看出,BswM管理各个模块,每个模块独立,降低耦合。 BswM 的主要功能包括: 模式管理:BswM 可以管理和控制 ECU 的不同模式,例如正常模式、备…

2024.4.5|牛客小白月赛90

2024.4.5|牛客小白月赛90 A.小A的文化节 B.小A的游戏 C.小A的数字 D.小A的线段&#xff08;easy version&#xff09; E.小A的任务 F.小A的线段&#xff08;hard version&#xff09; 心有猛虎&#xff0c;细嗅蔷薇。你好朋友&#xff0c;这里是锅巴的C\C学习笔记&#xff0c…

【鸿蒙 HarmonyOS】获取设备的地理位置

一、背景 获取移动设备的地理位置&#xff0c;包含&#xff1a;经度、维度、具体地理位置等&#xff0c;地理位置信息能在许多业务场景中被应用&#xff0c;如导航、地图服务、位置服务、社交媒体等。 下面以一个Demo例子&#xff0c;来实现获取设备地理位置的功能 官方文档…

无头单向非循环链表的实现

1.链表的结构 在用代码实现之前&#xff0c;我们要先了解这种链表的逻辑结构和物理结构&#xff0c; 在逻辑上我们能知道这种链表能够通过前一个节点的 next 来存储下一个节点的地址&#xff0c;从而能够找到下一个数据&#xff0c;这就是一种线性结构&#xff0c;我们可以把数…

智能感应门改造工程

今天记录一下物联网专业学的工程步骤及实施过程 智能感应门改造工程 1 规划设计1.1 项目设备清单1.2项目接线图 软件设计信号流 设备安装与调试工程函数 验收 1 规划设计 1.1 项目设备清单 1.2项目接线图 软件设计 信号流 设备安装与调试 工程函数 工程界面: using System; …