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 个场宽”的格式要求
)
