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

递归实现组合型枚举(DFS)

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

输入格式

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

输出格式

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

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

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

数据范围

n>0 ,
0≤m≤n ,
n+(n−m)≤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 

题目链接:93. 递归实现组合型枚举 - AcWing题库

学习链接:递推与递归 + DFS | 手把手带你画出递归搜索树_哔哩哔哩_bilibili 

解题思路: 
  1. 保证所有方案按字典序排序,且一个方案中后一个元素比前一个元素大
  2. 解决方案:每枚举到一个新位置,试探起始元素比前一个位置的元素+1
  3. 设置一个桶t[],容量为m个元素,装未被试探过且比前一个位置中的元素大的数
  4. 设置一个visited[],标记已访问过的元素(这题不用设置也可以)
  5. 得到一个方案后,即桶t[]装够了m个元素,结束搜索
  6. 重复 "撤出-装入" 这一操作,即回溯-搜索,撤出元素是为了腾出位置便于得到新的方案(在不同位置放置不同的元素),重新标记撤出的元素为未访问过 

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n;//总元素个数 
int m;//方案中元素个数
int t[30];//记录方案结果
int visited[30];//0 未访问,1 已访问void dfs(int pos,int start)
{//剪枝:当可选元素数量(n-start+1)<空位置数量(m-pos+1)时,咔擦掉(这题不剪也可以过) if(n-start+1<m-pos+1)	return ;//直接结束搜索 //如果方案中所枚举数量超过m个,终止搜索 if(pos>m){//输出方案for(int i=1;i<=m;i++)cout<<t[i]<<" ";cout<<endl;return ;//结束枚举 }for(int i=start;i<=n;i++){//这题不用设置visited[]t[pos]=i;//对下一个位置进行枚举,下一个位置的起始元素要比该位置的元素大dfs(pos+1,i+1);//撤出元素,便于新方案的选择t[pos]=0; }
} 
int main()
{cin>>n>>m;dfs(1,1);//从第一个位置且起始元素为 1 开始枚举方案 return 0;
}

 希望能帮助到各位同志,祝天天开心,学业进步!

相关文章:

递归实现组合型枚举(DFS)

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

【Java学习日记18】:三元运算符和运算符的优先级

一、三元运算符 2. 示例代码 例题1: 例题2: 二、运算符优先级 1. 优先级规则 Java 运算符的执行顺序由优先级决定&#xff0c;优先级高的先执行。 只要记住小括号优先级最大即可,以后就用这玩意 四、总结 运算符优先级&#xff1a;小括号 () 是最高优先级工具...

基于springboot放松音乐在线播放系统(源码+lw+部署文档+讲解),源码可白嫖!

摘要 本放松音乐在线播放系统采用B/S架构&#xff0c;数据库是MySQL&#xff0c;网站的搭建与开发采用了先进的Java进行编写&#xff0c;使用了Spring Boot框架。该系统从两个对象&#xff1a;由管理员和用户来对系统进行设计构建。前台主要功能包括&#xff1a;用户注册、登录…...

【Scratch编程系列】Scratch编程软件界面

Scratch是一款由麻省理工学院(MIT&#xff09; 设计开发的少儿编程工具。其特点是&#xff1a;使用者可以不认识英文单词&#xff0c;也可以不使用键盘&#xff0c;就可以进行编程。构成程序的命令和参数通过积木形状的模块来实现。用鼠标拖动指令模块到脚本区就可以了。 这个软…...

技术驱动革新,强力巨彩LED软模组助力创意显示

随着LED显示技术的不断突破&#xff0c;LED软模组因其独特的柔性特质和个性化显示效果&#xff0c;正逐渐成为各类应用场景的新宠。强力巨彩软模组R3.0H系列具备独特的可塑造型能力与技术创新&#xff0c;为商业展示、数字艺术、建筑装饰等领域开辟全新视觉表达空间。    LED…...

历年跨链合约恶意交易详解(三)——Nomad Bridge20220801

漏洞合约函数 /*** notice Given formatted message, attempts to dispatch* message payload to end recipient.* dev Recipient must implement a handle method (refer to IMessageRecipient.sol)* Reverts if formatted messages destination domain is not the Replicas d…...

Tensorflow、Pytorch与Python、CUDA版本的对应关系(更新时间:2025年4月)

更新时间:20250405 一、Tensorflow与Python 、CUDA版本对应关系 注意:从 TF 2.11 开始,Windows 不支持 CUDA 构建。要在 Windows 上使用 TensorFlow GPU,您需要在 WSL2 中构建/安装 TensorFlow 或将 tensorflow-cpu 与 TensorFlow-DirectML-Plugin 一起使用 1.1、CPU版本…...

FPGA实现按键切换流水灯不同亮灭模式

本文是一位fpga新手学习fpga的博客&#xff0c;写出这个shi山代码花了3个小时左右&#xff0c;途中学习了按键消抖、状态机等知识... 实现目标&#xff1a;通过按键控制led灯亮的不同模式&#xff0c;将每种模式用状态机表达。 代码如下&#xff1a; module led(input btn1,in…...

SeaTunnel系列之:部署SeaTunnel的Spark和Flink引擎

SeaTunnel系列之&#xff1a;部署SeaTunnel的Spark和Flink引擎 运行 SeaTunnel快速开始使用 Flink快速开始使用 Spark 运行 SeaTunnel 现在您已经下载了 SeaTunnel 二进制包和连接器插件。接下来&#xff0c;您可以选择不同的引擎选项来运行同步任务。 如果您使用 Flink 运行…...

“Pseudo Global Warming”:伪全球变暖PGW

“Pseudo Global Warming”&#xff1a;伪全球变暖PGW PGW方法概述&#x1f50d; 一、PGW 方法的定义&#x1f9e0; 二、PGW 方法的基本原理&#x1f6e0;️ 三、PGW 方法的主要步骤&#x1f4c8; 四、PGW 模拟时常涉及的变量&#x1f4ca; 五、PGW 方法的优/缺点&#x1f4da;…...

【Linux学习笔记】初识进程概念和进程PCB

【Linux学习笔记】初识冯诺依曼体系和进程PCB &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;Linux学习笔记 文章目录 【Linux学习笔记】初识冯诺依曼体系和进程PCB前言一. 冯诺依曼体系结构1.1 关于冯诺依曼体系的要点&#xff1a; 二. 操…...

deepseek回答ollama 下载模型的命令

ollama 下载模型的命令 已深度思考&#xff08;用时 20 秒&#xff09; 好的&#xff0c;我需要回答用户关于使用Ollama下载模型的命令的问题。首先&#xff0c;我需要回忆Ollama的基本用法。Ollama是一个用于本地运行大型语言模型的工具&#xff0c;支持多种模型如Llama、Mi…...

Kafka 中的生产者分区策略

Kafka 中的 生产者分区策略 是决定消息如何分配到不同分区的机制。这个策略对 Kafka 的性能、负载均衡、消息顺序性等有重要影响。了解它对于高效地使用 Kafka 进行消息生产和消费至关重要。 让我们一起来看 Kafka 中 生产者的分区策略&#xff0c;它如何工作&#xff0c;以及…...

Kafka 如何调优?

Kafka 的调优是个非常实用又容易踩坑的话题&#xff0c;涉及 Producer、Broker、Consumer、硬件、操作系统 等多个层面。我们可以从整体架构角度出发&#xff0c;按模块逐个给你讲清楚 实战建议。 &#x1f3af; Kafka 调优主要目标&#xff1a; 提高吞吐量降低延迟保证可靠…...

【机器学习】机器学习工程实战-第4章 特征工程

上一章&#xff1a;第3章 数据收集和准备 文章目录 4.1 为什么要进行特征工程4.2 如何进行特征工程4.2.1 文本的特征工程4.2.2 为什么词袋有用4.2.3 将分类特征转换为数字4.2.4 特征哈希4.2.5 主题建模4.2.6 时间序列的特征4.2.7 发挥你的创造力 特征工程是将原始样本转化为特…...

spring-cloud-alibaba-nacos-config使用说明

一、核心功能与定位 Spring Cloud Alibaba Nacos Config 是 Spring Cloud Alibaba 生态中的核心组件之一&#xff0c;专为微服务架构提供动态配置管理能力。它通过整合 Nacos 的配置中心功能&#xff0c;替代传统的 Spring Cloud Config&#xff0c;提供更高效的配置集中化管理…...

必刷算法100题之计算右侧小于当前元素的个数

题目链接 315. 计算右侧小于当前元素的 个数 - 力扣&#xff08;LeetCode&#xff09; 题目解析 计算数组里面所有元素右侧比它小的数的个数, 并且组成一个数组,进行返回 算法原理 归并解法(分治) 当前元素的后面, 有多少个比我小(降序) 我们要找到第一比左边小的元素, 这…...

OpenHarmony子系统开发 - DFX(三)

OpenHarmony子系统开发 - DFX&#xff08;三&#xff09; 五、HiTraceMeter开发指导 HiTraceMeter概述 简介 HiTraceMeter在OpenHarmony中&#xff0c;为开发者提供业务流程调用链跟踪的维测接口。通过使用该接口所提供的功能&#xff0c;可以帮助开发者迅速获取指定业务流…...

[ctfshow web入门] web6

前置知识 入口点(目录)爆破 还记得之前说过网站的入口的吗&#xff0c;我们输入url/xxx&#xff0c;其中如果url/xxx存在&#xff0c;那么访问成功&#xff0c;证明存在这样一个入口点&#xff1b;如果访问失败则证明不存在此入口点。所以我们可以通过遍历url/xxx&#xff0c;…...

完整的Python程序,它能够根据两个Excel表格(假设在同一个Excel文件的不同sheet中)中的历史数据来预测未来G列数字

下面是一个完整的Python程序&#xff0c;它能够根据两个Excel表格&#xff08;假设在同一个Excel文件的不同sheet中&#xff09;中的历史数据来预测未来G列数字。此程序采用多模型验证&#xff0c;并且具备自我学习和动态参数调整的功能。最终会输出12个可能的数字范围及其出现…...

设计模式简述(一)设计原则

设计模式简述 6大基本设计原则单一职责原则依赖倒置原则依赖传递方式 里氏替换原则接口隔离原则迪米特法则开闭原则 6大基本设计原则 单一职责原则 一个接口、一个类、一个方法的功能尽量保证原子性。 至于这个度自己把握&#xff0c;没有绝对的标准。 通常可以将同一类、同…...

哈希表(Hashtable)核心知识点详解

1. 基本概念 定义&#xff1a;通过键&#xff08;Key&#xff09;直接访问值&#xff08;Value&#xff09;的数据结构&#xff0c;基于哈希函数将键映射到存储位置。 核心操作&#xff1a; put(key, value)&#xff1a;插入键值对 get(key)&#xff1a;获取键对应的值 remo…...

论文阅读笔记:Denoising Diffusion Implicit Models (5)

0、快速访问 论文阅读笔记&#xff1a;Denoising Diffusion Implicit Models &#xff08;1&#xff09; 论文阅读笔记&#xff1a;Denoising Diffusion Implicit Models &#xff08;2&#xff09; 论文阅读笔记&#xff1a;Denoising Diffusion Implicit Models &#xff08…...

JDK8卸载与安装教程(超详细)

JDK8卸载与安装教程&#xff08;超详细&#xff09; 最近学习一个项目&#xff0c;需要使用更高级的JDK&#xff0c;这里记录一下卸载旧版本与安装新版本JDK的过程。 JDK8卸载 以windows10操作系统为例&#xff0c;使用快捷键winR输入cmd&#xff0c;打开控制台窗口&#xf…...

R语言网状Meta分析---Meta回归(1)(基于gemtc)

示例&#xff1a; library(gemtc) help(package"gemtc") # Fixed effect meta-regression for heart failure prevention str(hfPrevention) regressor <- list(coefficientshared,variablesecondary,controlcontrol) model <- mtc.model(hfPrevention,type&q…...

通过AOP切面,切点,反射填充公共字段

在项目中&#xff0c;我们通常会实现员工管理和菜品管理等基础服务功能。这些服务在操作数据库时&#xff0c;往往需要记录一些通用字段&#xff0c;比如&#xff1a; 创建人ID&#xff08;create_user_id&#xff09; 修改人ID&#xff08;update_user_id&#xff09; 创…...

CNN 中感受野/权值共享是什么意思?

这个问题问得非常到位&#xff01;&#x1f31f; 在 CNN&#xff08;卷积神经网络&#xff09;中&#xff0c;“感受野” 和 “权值共享” 是两个核心概念&#xff0c;它们一起构建了 CNN 在图像处理领域强大能力的基础。 &#x1f9e0; 一句话解释&#xff1a; • 感受野&…...

【蓝桥杯速成】日期问题(填空题) + 真题讲解 python

众所周知&#xff0c;蓝桥杯有两道填空题&#xff0c;还特别喜欢考日期问题 什么&#xff1f;你还在使用计算器手算&#xff1f; 那你将会考虑闰年、大小月等等细节到头昏眼花 最后还比答案大或小1 寄&#xff01; 接下来我来告诉你正确的做法 基础知识 python自带datetime库…...

C++基础讲解

C基础讲解 序言1 命名空间1.1 命名空间的作用1.2,命名空间的定义1.3 命名空间的使用 2 C输入与输出3 缺省参数4 函数重载5 引用5.1 引用的概念与特性5.2 引用的使用5.2.1 引用传参5.2.2 引用做返回值5.2.2.1采用引用返回&#xff1a;5.2.2.2采用值返回的情形&#xff1a;5.2.2.…...

【代码模板】判断C语言中文件是否存在?错误:‘F_OK’未声明如何处理?(access;#include “unistd.h“)

#include "stdio.h" #include "unistd.h"int main(int argc, char *argv[]) {if (access("./1.cpp", F_OK) -1) {printf("not exist\n");} else {printf("exist\n");} }报错 错误&#xff1a;‘F_OK’未声明 需要包含#inc…...

form实现note笔记本新建保存加密功能

说明&#xff1a; 我希望用form实现笔记本新建保存加密功能 笔记管理应用&#xff0c;具备创建、保存、删除笔记的功能&#xff0c;并且有简单的加密保护。 ​1.笔记管理&#xff1a;1.1新建笔记&#xff1a;清除标题和内容&#xff0c;取消列表选择。1.2保存笔记&#xff1a;验…...

【算法竞赛】状态压缩型背包问题经典应用(蓝桥杯2019A4分糖果)

在蓝桥杯中遇到的这道题&#xff0c;看上去比较普通&#xff0c;但其实蕴含了很巧妙的“状态压缩 背包”的思想&#xff0c;本文将从零到一&#xff0c;详细解析这个问题。 目录 一、题目 二、思路分析&#xff1a;状态压缩 最小覆盖 1. 本质&#xff1a;最小集合覆盖问题…...

【C++初阶篇】C++中c_str函数的全面解析

C中c_str函数的全面解析 1. c_str()函数的定义与原型2. c_str()函数的返回值特性3 c_str()函数的使用场景3.1 与C标准库函数交互3.2 文件操作3.3 系统调用 4. c_str()函数的注意事项4.1 返回指针的只读性4.2 生命周期问题4.3 空字符串处理4.4 避免直接赋值给char* 5. c_str()函…...

Python 匿名函数(Lambda函数)

什么是匿名函数 匿名函数&#xff08;也称为lambda函数&#xff09;是Python中的一种小型匿名函数&#xff0c;它可以接受任意数量的参数&#xff0c;但只能有一个表达式。 语法格式&#xff1a; lambda arguments: expression使用场景 简单函数逻辑&#xff1a;当函数逻辑…...

java高并发------守护线程Daemon Thread

文章目录 1.概念2.生命周期与行为2. 应用场景3. 示例代码4. 注意事项 1.概念 Daemon &#xff1a; 滴门 在Java中&#xff0c;线程分为两类&#xff1a;用户线程(User Thread)和守护线程(Daemon Thread)。 守护线程是后台线程&#xff0c;主要服务于用户线程&#xff0c;当所…...

RocketMQ初认识

ProducerCustomerNameServer: Broker的注册服务发现中心BrokerServer:主要负责消息的存储、投递和查询以及服务高可用保证 RocketMQ的集群部署&#xff1a; 单个master的分支多个Master 模式&#xff1a;集群中有多个 Master 节点&#xff0c;彼此之间相互独立。生产者可以将消…...

K8s的BackUP备份

文章目录 1、kubeadm 安装的单 master 节点数据备份和恢复方式2、Velero 工具3、Velero 服务部署4、备份还原数据 ETCD备份/还原有多种类型&#xff0c;取决于你 k8s 集群的搭建方式 1、kubeadm 安装的单 master 节点数据备份和恢复方式 拷贝 etcdctl 至 master 节点&#xf…...

Photoshop 快捷键指南

Photoshop 快捷键指南 放大缩小 按住 Ctrl 鼠标滚轮快捷键 Z 鼠标左键往左往右Ctrl 放大&#xff0c; Ctrl - 缩小 套索工具 快捷键 L鼠标左键绘制按住 ctrl&#xff0c;松开鼠标左键&#xff0c;继续绘制直线绘制完成之后&#xff0c;按住ctrl&#xff0c;鼠标左键继续绘…...

Openlayers:海量图形渲染之图片渲染

最近由于在工作中涉及到了海量图形渲染的问题&#xff0c;因此我开始研究相关的解决方案。在这个过程中我阅读了文章 《Openlayers海量矢量面渲染优化》了解到了利用Canvas在前端生成图片渲染的思路&#xff0c;后来我又从同事那里了解到了后端生成图片渲染的思路。我认为这两种…...

自定义组件触发饿了么表单校验

饿了么的表单控件&#xff0c;如果存在自定义组件更改了值&#xff0c;例如在el-from中存在原生input组件很有可能没法触发表单校验&#xff0c;下拉框或者弹框组件仍然是报红边框。 这是因为饿了么的输入框或者下拉框更改值的时候会自动触发表单校验&#xff0c;但是封装过后的…...

【C++】从零实现Json-Rpc框架(1)

目录 一、项目介绍 二、技术选型 1. RPC的实现方案&#xff1a; 2. 网络传输的参数和返回值怎么映射到对应的RPC 接口上&#xff1f; 3. 网络传输怎么做&#xff1f; 4. 序列化和反序列化&#xff1f; 三、开发环境 四、环境搭建 Ubuntu-22.04 环境搭建 项目汇总&…...

[实战] linux驱动框架与驱动开发实战

linux驱动框架与驱动开发实战 Linux驱动框架与驱动开发实战一、Linux驱动框架概述1.1 Linux驱动的分类1.2 Linux驱动的基本框架 二、Linux驱动关键API详解2.1 模块相关API2.2 字符设备驱动API2.3 内存管理API2.4 中断处理API2.5 PCI设备驱动API 三、Xilinx XDMA驱动开发详解3.1…...

【详细】MySQL 8 安装解压即用 (包含MySQL 5 卸载)

卸载MySQL 1.卸载 2.安装目录删除残余文件&#xff08;当初安装的位置&#xff09; 3.删除programData下面的mysql数据文件 4.检查mysql服务是否存在&#xff0c;如果存在则删除&#xff08;先暂停mysql服务&#xff09; sc delete mysql 5.删除注册表中残留信息 安装MySQL 8&…...

Linux:(五种IO模型)

目录 一、对IO的重新认识 二、IO的五种模型 1.阻塞IO 2.非阻塞IO 3.信号驱动IO 4.IO多路转接 5.异步IO 6.一些概念的解释 三、非阻塞IO的代码实现 1.fcntl 2.实现主程序 一、对IO的重新认识 如果有人问你IO是什么&#xff0c;你该怎么回答呢&#xff1f; 你可能会说…...

初识数据结构——Java包装类与泛型:从入门到源码解析

【深入浅出】Java包装类与泛型&#xff1a;从入门到源码解析 &#x1f31f; 一、开篇一问&#xff1a;为什么我们需要包装类&#xff1f; Java作为一门"面向对象"的语言&#xff0c;却保留了8个"非对象"的基本数据类型&#xff08;有传言说&#xff0c;是…...

【计算机网络】Linux配置SNAT策略

什么是NAT&#xff1f; NAT 全称是 Network Address Translation&#xff08;网络地址转换&#xff09;&#xff0c;是一个用来在多个设备共享一个公网 IP上网的技术。 NAT 的核心作用&#xff1a;将一个网络中的私有 IP 地址&#xff0c;转换为公网 IP 地址&#xff0c;从而…...

与 AI 共舞:解锁自我提升的无限可能

与 AI 共舞&#xff1a;解锁自我提升的无限可能 在数字化浪潮的汹涌冲击下&#xff0c;人工智能&#xff08;AI&#xff09;正以前所未有的速度重塑着世界的每一个角落。从日常生活的点滴便利到复杂工作的高效推进&#xff0c;AI 的力量无处不在。然而&#xff0c;面对 AI 的强…...

Android学习总结之算法篇五(字符串)

字符串求回文字串数目 public class CountPalindromicSubstrings {/*** 此方法用于计算字符串中回文子串的数量* param s 输入的字符串* return 回文子串的数量*/public static int countSubstrings(String s) {// 若输入字符串为空或长度为 0&#xff0c;直接返回 0if (s nu…...

使用人车关系核验API快速核验车辆一致性

一、 引言 随着车辆交易的日益频繁&#xff0c;二手车市场和金融领域的汽车抵押业务蓬勃发展。然而&#xff0c;欺诈和盗窃行为也时有发生&#xff0c;给行业带来了不小的冲击。例如&#xff0c;3月20日央视曝光的“新能源车虚假租赁骗补”产业链&#xff0c;以及某共享汽车平…...

day 8 TIM定时器

一、STM32 定时器概述 1. 定时器的概述定时器的基本功能&#xff0c;但是 STM32 的定时器除了具有定时功能之外&#xff0c;也具有定时器中断功能&#xff0c;还具有输入捕获&#xff08;检测外部信号&#xff09;以及输出比较功能&#xff08;输出不同的脉冲&#xff09;&…...