P1706 全排列问题-北京尧图网络

记录159#includebits/stdc.h using namespace std; int path[15]; bool vis[15]; int n; void dfs(int cnt){ if(cntn){ for(int i1;in;i) cout path[i]; cout\n; return; } for(int i1;in;i){ if(vis[i]0){ vis[i]1; path[cnt]i; dfs(cnt1); vis[i]0; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; dfs(1); return 0; }题目传送门https://www.luogu.com.cn/problem/P1706前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的深度优先搜索DFS与回溯算法入门题。问题转化排列树模型生成 1∼n 的全排列本质上是在构建一棵深度为 nn 的“排列树”。我们在树的每一层对应排列中的每一个位置从 1∼n中选择一个还没有被使用过的数字填入。算法设计DFS 状态标记使用一个数组path来记录当前正在构建的排列序列。使用一个布尔数组vis来记录哪些数字已经被用过了避免重复。每次递归时枚举 1∼n 的所有数字。如果某个数字没有被用过就把它放入path中标记为已用然后进入下一层递归。当递归深度达到 n 时说明一个完整的排列已经生成将其输出。回溯的关键从下一层递归返回后必须将刚才标记为已用的数字重新标记为未用vis[i] 0以便在后续的循环中尝试其他数字。代码分块详细解释1. 全局变量定义#includebits/stdc.h using namespace std; int path[15]; bool vis[15]; int n;详细分析path数组用来存放当前正在生成的排列序列vis数组visit的缩写是一个状态标记数组vis[i] 1表示数字 ii 已经在当前排列中被使用过0表示未使用。由于题目保证 n≤9n≤9 数组开 15 足够。2. 核心逻辑DFS 搜索与回溯void dfs(int cnt){ if(cnt n){ for(int i 1; i n; i) cout path[i]; cout \n; return; } for(int i 1; i n; i){ if(vis[i] 0){ vis[i] 1; path[cnt] i; dfs(cnt 1); vis[i] 0; // 回溯撤销选择恢复现场 } } }详细分析这是代码的灵魂完美体现了回溯法“选择 - 递归 - 撤销选择”的三步曲。递归终止条件当cnt n时说明前 nn 个位置都已经填满了数字一个完整的排列已经生成。此时按照题目要求的“每个数字保留 5 个场宽”即前面加 4 个空格输出path数组。枚举与剪枝在当前位置cnt我们尝试枚举 1∼n1∼n 的所有数字。if(vis[i] 0)保证了我们只会选择那些尚未被使用的数字。状态更新与递归选定数字i后将其标记为已用vis[i] 1存入路径path[cnt] i然后进入下一层dfs(cnt 1)去填充下一个位置。回溯恢复现场当dfs(cnt 1)执行完毕返回时说明以当前数字i为起点的所有排列都已经生成完了。为了尝试下一个数字我们必须把i的状态恢复为未使用vis[i] 0这就是回溯的核心。3. 主函数与启动搜索int main(){ ios::sync_with_stdio(false); cin.tie(0); cin n; dfs(1); return 0; }详细分析读入 nn 后直接从dfs(1)开始表示从排列的第 1 个位置开始填数。由于我们是从 1 到 n 顺序枚举数字的所以生成的排列天然就是字典序的。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点路径记录path[cnt] i记录当前正在构建的排列序列保证了在到达叶子节点时能够完整地输出整个排列状态标记vis[i] 1标记数字 i 已被使用保证了“所产生的任一数字序列中不允许出现重复的数字”回溯恢复vis[i] 0撤销对数字 i 的使用标记使得数字 ii 可以在其他分支中被再次使用是生成全排列的关键字典序保证for(int i 1; i n; i)从小到大枚举数字保证了输出的排列序列天然符合字典序要求无需额外排序格式化输出cout path[i]每个数字前输出4个空格完美契合题目“每个数字保留 5 个场宽”的格式要求

P1706 全排列问题

相关推荐

【单片机毕业设计推荐】基于 51/STM32 单片机的智能台灯与温控风扇控制系统设计，基于 51/STM32 单片机的人体感应环境调控装置设计与实现（011903）

《闻香识女人》4K修复版观影指南：细节解析与经典场景解读

从客户管理到经营闭环：2026年CRM选型的路线分化与厂商解析

更多资讯

Triton Inference Server C API 内嵌模式指南：通过 libtritonserver.so 将推理服务直接集成进 C/C++ 应用

图腾柱驱动电路设计：MOSFET高效开关的工程实践指南

国产宇树科技！全球顶流四足机器人独角兽

AI陪伴机器人JPA实体映射与ddl-auto的利与弊

大模型API调用中的Token成本优化实践

AI陪伴机器人API设计-api-users到api-alerts的二十个接口

今日更新

Play Framework 迁移指南：移除 GlobalSettings，全面转向依赖注入（Scala 与 Java）

Numba 类型推断机制详解：从 Numba IR 到编译期类型重建的完整原理与实践

企业级项目dragonballz_e159-1的技术架构与实现方案

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？