【C算法打怪专栏】洛谷 P1706 全排列问题DFS经典回溯题目概述题目链接P1706 全排列问题核心考点深度优先搜索DFS、回溯算法、格式化输出setw解题思路与易错点分析1. 递归与回溯框架求解 1 ~ n 的全排列是经典的状态空间树搜索问题搜索状态用step表示当前正在填写第几个位置。边界条件当step n时说明成功生成了一组合法排列输出结果并终止递归。状态标记与还原回溯使用vis[i]标记数字i是否已被选过。递归进入下一层dfs(step 1)前标记vis[i] true。从下一层递归返回后必须取消标记vis[i] false恢复现场以供后续分支尝试。2. 踩坑与易错点汇总WA / CE 原因变量作用域遮蔽局部变量遮盖全局变量问题在main函数内部重新声明了int n;导致cin n;读入的是局部变量而dfs中访问的全局变量n依然为默认值0。后果直接满足step n终止条件无任何搜索输出。解决在main函数中直接使用全局变量cin n;不要重声明。输出格式处理题目要求“每个数字保留 5 个场宽”。标准实现cout setw(5) a[i];需包含头文件iomanip。常见错误cout setw(5) a[i] ;多输出了多余空格导致 OJ 判定格式错误WA。正确代码实现AC#includeiostream#includeiomanip#includevectorusingnamespacestd;intn;// 全局变量 n供 dfs 函数读取boolvis[15];// 标记数组vis[i] 表示数字 i 是否已被使用vectorinta(15);// 存储当前排列路径voiddfs(intstep){// 递归边界填满 1~n 共 n 个位置if(stepn){for(inti1;in;i){coutsetw(5)a[i];// 保留 5 个场宽输出不额外加空格}cout\n;return;}// 枚举数字 1 到 nfor(inti1;in;i){if(!vis[i]){a[step]i;// 选择数字 i 填入第 step 位vis[i]true;// 标记使用dfs(step1);// 递归填下一个位置vis[i]false;// 回溯撤销标记恢复现场}}}intmain(){// I/O 加速ios::sync_with_stdio(false);cin.tie(nullptr);cinn;// 直接读入全局变量 ndfs(1);// 从第 1 个位置开始搜索return0;}