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

AcWing93. 递归实现组合型枚举:输出从1~n中随机选出的m个整数

题目

从 1∼ n n n n n n 个整数中随机选出 m m m 个,输出所有可能的选择方案。

输入格式

两个整数 n , m , n,m, n,m, 在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案,每行 1 个。

首先,同一行内的数升序排列,相邻两个数用一个空格隔开。

其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如 1 3 5 7 排在 1 3 6 8 前面)。

数据范围

n > 0 n>0 n>0,
0 ≤ m ≤ n 0≤m≤n 0mn,
n + ( n − m ) ≤ 25 n+(n−m)≤25 n+(nm)25

输入样例

5 3

输出样例

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

思考题:如果要求使用非递归方法,该怎么做呢?

思路

思路类似于AcWing92,但是多了一个个数限制。

另外,因为升序排列,所以可以枚举每个数,就可以形成一棵递归搜索树。可以枚举当前在哪层,以及当前以哪个数开始继续往下搜。

代码

#include <bits/stdc++.h>
#include <vector>
using namespace std;vector<int> chosen; //被选择的数void print_subset(int n, int m, int x) {//剪枝:无解的情况//选择超过了m个,或即使再选上剩余的所有数也不够m个,则无解//这条剪枝保证一旦进入无解的分支就会立刻返回if (chosen.size() > m || chosen.size() + (n - x + 1) < m) {return ;}if (x == n + 1) {for (int i = 0; i < chosen.size(); i++) {printf("%d ", chosen[i]);}printf("\n");return ;}//“选num” 分支chosen.emplace_back(x);//记录num已被选择print_subset(n, m, x + 1); 求解子问题chosen.pop_back(); ///回溯到上一问题之前,还原现场//“不选num” 分支print_subset(n, m, x + 1);}int main() {int n, m;scanf("%d%d", &n, &m);print_subset(n, m, 1);return 0;
}

因为剪枝,时间复杂度从 2 n 2^n 2n 降低为 C n m C_n^m Cnm

递归搜索树写法:

#include <cstdio>
using namespace std;const int N = 30;
int path[N]; //存储路径(选择的数)
int n, m;void dfs(int u, int start) { //u当前层数,start当前在哪个数 if (u > m) { //已经找到了m个数for (int i = 1; i <= m; i++) {printf("%d ", path[i]);}puts("");} else {for (int i = start;  i <= n; i++) {path[u] = i; //当前层选择的数是idfs(u + 1, i + 1);path[u] = 0; //恢复现场}}
}int main() {scanf("%d%d", &n, &m);dfs(1, 1);return 0;
}

相关文章:

AcWing93. 递归实现组合型枚举:输出从1~n中随机选出的m个整数

题目 从 1∼ n n n 这 n n n 个整数中随机选出 m m m 个&#xff0c;输出所有可能的选择方案。 输入格式 两个整数 n , m , n,m, n,m, 在同一行用空格隔开。 输出格式 按照从小到大的顺序输出所有方案&#xff0c;每行 1 个。 首先&#xff0c;同一行内的数升序排列&a…...

Java修仙传之Flink篇

大道三千:最近我修Flink 目前个人理解&#xff1a; 处理有界&#xff0c;无界流的工具 FLINK&#xff1a; FLINK定义&#xff1a; Flink特点 Flink分层API 流的定义 有界数据流&#xff08;批处理&#xff09;&#xff1a; 有界流&#xff1a;数据结束了&#xff0c;程序也…...

网络新闻发稿为何经久不衰?

有的老板可能看不到新闻营销的直接回报&#xff0c;一直不乐意在此方面投入&#xff0c;但是却看到竞争对手一直在搞新闻营销&#xff0c;也就安排个PR做做新闻公关。小马识途营销顾问观察&#xff0c;自互联网诞生以来&#xff0c;新闻营销一直是网络营销工作中的一个重点。 如…...

Java SimpleDateFormat 中英文时间格式化转换

SimpleDateFormat是一个以与语言环境有关的方式来格式化和解析日期的具体类。它允许进行格式化&#xff08;日期 -> 文本&#xff09;、解析&#xff08;文本 -> 日期&#xff09;和规范化。 SimpleDateFormat使得可以选择任何用户定义的日期-时间格式的模式。但是&…...

机器学习-基本知识

 任务类型 ◼ 有监督学习(Supervised Learning) 每个训练样本x有人为标注的目标t&#xff0c;学习的目标是发现x到t的映射&#xff0c;如分类、回归。 ◼ 无监督学习(Unsupervised Learning) 学习样本没有人为标注&#xff0c;学习的目的是发现数据x本身的分布规律&#xf…...

Xilinx 7 系列 1.8V LVDS 和 2.5V LVDS 信号之间的 LVDS 兼容性

如果通过LVDS进行接口&#xff0c;可以按照以程图中的步骤操作&#xff0c;以确保满足正确使用LVDS的所有要求。 40191 - 7 系列 - 1.8V LVDS 和 2.5V LVDS 信号之间的 LVDS 兼容性 与LVDS兼容驱动器和接收器连接时&#xff0c;7系列LVDS和LVDS_25输入和输出应该不存在兼容性问…...

R语言在生态环境领域中的实践技术应用

R语言作为新兴的统计软件&#xff0c;以开源、自由、免费等特点风靡全球。生态环境领域研究内容广泛&#xff0c;数据常多样而复杂。利用R语言进行多元统计分析&#xff0c;从复杂的现象中发现规律、探索机制正是R的优势。为此&#xff0c;以鱼类、昆虫、水文、地形等多样化的生…...

ChineseChess.2023.10.31.01

中国象棋残局模拟器&#xff1a;黑双卒压禁区 中国象棋残局模拟器ChineseChess.2023.10.31.01...

数据库扩展语句和约束方式以及用户管理

数据库扩展语句和约束方式以及用户管理 create TABLE if not exists ky32 ( id int(4) zerofill primary key auto_increment, name varchar(10) not null, cradid int(18) not null unique key, hobby varchar (50) ); auto_increment&#xff1a;表示该字段可以自增长&…...

JMM 简单理解

JMM 简单理解 1 Java 内存模型 Java 内存模型&#xff08;Java Memory Model&#xff0c;JMM&#xff09;&#xff0c;主要为了屏蔽各种硬件和操作系统的内存差异&#xff0c;以实现让 Java 程序在各种平台下都能达到一致的内存访问效果&#xff0c;而设计的 2 工作内存与主内…...

微软Azure文本转音频,保存成MP3文件【代码python3】

标签&#xff1a; 文本转音频并保存mp3文件&#xff1b; 微软Azure&#xff1b; 微软Azure可以将文本转音频&#xff0c;并保存mp3文件&#xff0c;直接上代码 代码格式&#xff1a;python 3 import os import azure.cognitiveservices.speech as speechsdk# This example re…...

基于单片机的超声波探伤仪设计

摘要 超声波探伤仪是目前工业制造和现代化检测的重要途径之一&#xff0c;广泛的应用在质量检测和产品检测中&#xff0c;通过使用其产品能够有效地降低产品次品的风险。尽管随着电子技术的发展&#xff0c; 国内出现了一些数字化的超声检测仪器&#xff0c;但其数据处理及扩展…...

idea的设置

1.设置搜索encoding,所有编码都给换为utf-8 安装插件 eval-reset插件 https://www.yuque.com/huanlema-pjnah/okuh3c/lvaoxt#m1pdA 设置活动模板,idea有两种方式集成tomcat,一种是右上角config配置本地tomcat,一种是插件,如果使用插件集成,则在maven,pom.xml里面加上tomcat…...

高等数学啃书汇总重难点(八)向量代数与空间解析几何

持续更新&#xff0c;高数下第一章&#xff0c;整体来说比较简单&#xff0c;但是需要牢记公式&#xff0c;切莫掉以轻心~ 一.向量平行的充要条件 二.向量坐标的线性运算 三.向量的几何性质 四.数量积 五.向量积 六.混合积 七.曲面方程 八.空间曲线方程 九.平面的点法式方程 十…...

C#开发DLL,CAPL调用(CAPL>> .NET DLL)

文章目录 展示说明新建类库工程C# 代码生成dllCAPL脚本调用dll,输出结果展示 ret为dll里函数返回的值。 说明 新建类库工程 在visual studio中建立。 C# 代码 using...

0-1背包问题【穷举法+二维dp数组】

问题描述&#xff1a; 使用穷举法解决0/1背包问题。问题描述&#xff1a;给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn} 的物品和一个容量为C的背包&#xff0c;求这些物品中的一个最有价值的子集&#xff0c;且要能够装到背包中。 穷举法&#xff1a;每件物品装还是…...

nodejs+vue+python+php基于微信小程序的在线学习平台设计与实现-计算机毕业设计

困扰管理层的许多问题当中,在线学习也是不敢忽视的一块。但是管理好在线学习又面临很多麻烦需要解决,例如&#xff1a;如何在工作琐碎,记录繁多的情况下将在线学习的当前情况反应给课程问题管理员决策,等等。 流,开发一个在线学习平台小程序一方面的可能会更合乎时宜,另一方面来…...

Spring学习笔记2 Spring的入门程序

Spring学习笔记1 启示录_biubiubiu0706的博客-CSDN博客 Spring官网地址:https://spring.io 进入github往下拉 用maven引入spring-context依赖 写spring的第一个程序 引入下面依赖,好比引入Spring的基本依赖 <dependency><groupId>org.springframework</groupId&…...

【Linux】虚拟机安装Linux、客户端工具及Linux常用命令(详细教程)

一、导言 1、引言 Linux是一个开源的操作系统内核&#xff0c;它最初由芬兰计算机科学家Linus Torvalds于1991年开发。Linux不同于传统的商业操作系统&#xff0c;它常用于服务器、嵌入式系统和个人电脑等各种平台。 Linux具有很多优点&#xff0c;包括稳定性、安全性和可定制…...

Day 47 动态规划 part13

Day 47 动态规划 part13 解题理解300674718 3道题目 300. 最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组 解题理解 300 dp[i]被设置为以nums[i]为结尾的最长递增子序列长度。 class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums) …...

解锁Switch模拟潜能:Ryujinx架构深度解析与实战优化

解锁Switch模拟潜能&#xff1a;Ryujinx架构深度解析与实战优化 【免费下载链接】Ryujinx 用 C# 编写的实验性 Nintendo Switch 模拟器 项目地址: https://gitcode.com/GitHub_Trending/ry/Ryujinx Ryujinx作为一款采用C#开发的开源Nintendo Switch模拟器&#xff0c;通…...

Leather Dress Collection惊艳效果:Leather_Romper皮连体衣+户外场景自然光渲染

Leather Dress Collection惊艳效果&#xff1a;Leather_Romper皮连体衣户外场景自然光渲染 1. 项目介绍 Leather Dress Collection 是一个基于Stable Diffusion 1.5的LoRA模型集合&#xff0c;专门用于生成各种皮革服装风格的图像。这个系列由Stable Yogi开发&#xff0c;包含…...

Dual-Tree Agent RAG:可控、可解释、可验证

从文本检索到方法推理的跃迁 传统RAG系统将文档切分为平面文本块&#xff0c;通过向量相似度检索来增强大模型生成。这种模式在简单事实问答中表现良好&#xff0c;却难以应对需要全局结构理解、跨章节整合和方法论复用的复杂创新任务。现有改进方案如RAPTOR&#xff08;层次摘…...

多模态扩展:OpenClaw+GLM-4.7-Flash处理图片信息

多模态扩展&#xff1a;OpenClawGLM-4.7-Flash处理图片信息 1. 为什么需要多模态能力 上周我在整理产品截图时遇到一个典型问题&#xff1a;需要从200多张UI截图中提取所有按钮文字和位置信息。手动操作不仅耗时&#xff0c;还容易遗漏细节。这让我开始思考——能否让OpenCla…...

开源电池管理系统:SmartBMS的技术创新与实践应用

开源电池管理系统&#xff1a;SmartBMS的技术创新与实践应用 【免费下载链接】SmartBMS Open source Smart Battery Management System 项目地址: https://gitcode.com/gh_mirrors/smar/SmartBMS SmartBMS是一套开源智能电池管理系统&#xff0c;专为锂离子电池组&#…...

LabVIEW新手避坑指南:用For循环和数组搞定水仙花数,别再手动算啦!

LabVIEW实战&#xff1a;用For循环与数组高效求解水仙花数的5个关键技巧 水仙花数这个经典的编程练习题&#xff0c;在文本编程语言中可能只需十几行代码&#xff0c;但切换到LabVIEW的图形化编程环境时&#xff0c;不少初学者会陷入连线混乱和逻辑纠结。本文将从实际工程视角…...

OpCore-Simplify:如何用四步自动化流程解决黑苹果配置的三大核心挑战

OpCore-Simplify&#xff1a;如何用四步自动化流程解决黑苹果配置的三大核心挑战 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 对于黑苹果爱好者来说…...

用MATLAB从零实现六足机器人步态:交替三角与波动步态代码详解

用MATLAB从零实现六足机器人步态&#xff1a;交替三角与波动步态代码详解 六足机器人因其卓越的稳定性和地形适应能力&#xff0c;在野外勘探、灾难救援等领域展现出巨大潜力。而步态规划作为机器人运动控制的核心&#xff0c;直接决定了机器人的移动效率和稳定性。本文将带您从…...

ChatBI 开源产品实战解析:从语义层到Agent,如何选择你的AI数据助手?

1. 为什么企业需要AI数据助手&#xff1f; 想象一下这个场景&#xff1a;市场部的小王需要统计上季度各区域的销售数据&#xff0c;他对着Excel表格里密密麻麻的数字发愁&#xff0c;不得不找IT部门帮忙写SQL查询。三天后拿到数据时&#xff0c;业务窗口期已经错过——这是很多…...

Llama-3.2V-11B-cot企业级应用:双卡4090支撑的生产环境视觉推理服务搭建

Llama-3.2V-11B-cot企业级应用&#xff1a;双卡4090支撑的生产环境视觉推理服务搭建 1. 项目概述 Llama-3.2V-11B-cot是基于Meta最新多模态大模型开发的高性能视觉推理工具&#xff0c;专为企业级生产环境设计。该工具针对双卡NVIDIA RTX 4090环境进行了深度优化&#xff0c;…...