蓝桥杯备赛：Day5-P1706 全排列问题

算法笔记P1706 全排列问题 (DFS 基础)1. 题目描述P1706 全排列问题 - 洛谷输出1 ∼ N 1 \sim N1∼N的所有全排列要求每个数字占5 个场宽排列按字典序从小到大输出。2. 核心代码 (C 版本)#include bits/stdc.h using namespace std; typedef long long ll; ll N; ll ans[15]; // 记录当前位置存了哪个数字 bool used[15]; // 标记数字 i 是否已被使用 void dfs(int position) { // 1. 递归出口当位置超过 N 时说明 N 个坑位已填满 if(position N) { for(int i 1; i N; i) { cout setw(5) ans[i]; // 核心格式控制 } cout \n; return; // 功成身退回溯到上一层 } // 2. 尝试在当前位置填入数字 i for(int i 1; i N; i) { if(!used[i]) // 只有没用过的数字才能填入 { ans[position] i; // 填入数字 used[i] true; // 标记为已占用 dfs(position 1); // 递归进入下一个位置 used[i] false; // 【核心回溯】撤销标记释放数字 } } } void solve() { if(!(cin N)) return; dfs(1); } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int _ 1; while(_--) { solve(); } return 0; }3. 核心考点与注意事项DFS 递归模型本题体现了 DFS 最经典的思想——“不撞南墙不回头”。通过递归不断深入直到触发出口条件。回溯机制 (Backtracking)used[i] false;是整段代码的灵魂。它保证了在完成一种排列并返回后之前使用的数字能被释放从而参与到其他分支的排列中。状态维护position记录递归的深度即当前的坑位。i记录横向的选择范围即手里的数字。格式要求setw(5)是iomanip库中的函数万能头已包含用于满足题目严格的场宽要求。️ 深度拆解第二层工人的“工作日志”假设N 3 N3N3第二层工人的任务是填好第二个坑位ans[2]。第一阶段尝试数字 2开始循环工人看手里有哪些牌。数字1 11被第一层拿走了数字2 22还没人用。填坑他在第二个坑里填入2ans[2] 2并标记used[2] true。派发任务他大喊一声“第三层剩下的交给你了”然后调用dfs(3)。原地待命此时第二层工人的程序暂停在了dfs(3)这一行他进入了漫长的等待。第二阶段回火Backtracking任务返回过了一会儿第三层跑完回来了也就是1 2 3已经打印完了。苏醒第二层工人“苏醒”过来接着执行dfs(3)下面的代码。撤销操作他执行used[2] false。这意味着他把数字2从坑里拿了出来重新放回手里。这一步极其关键因为它让数字 2 重新变回了“可用状态”。第三阶段开启新分支i 变成 3继续循环因为他还在for循环里执行完刚才那两行后i发生了。寻找下一张牌现在i变成了3。检查可用性他发现数字3 33也没被用过used[3]是false。新的尝试他在第二个坑里填入新的数字ans[2] 3。标记used[3] true。再次大喊“第三层我又来了”调用dfs(3)。4. 易错点回顾 (My Mistakes)1. return 位置导致的“截断”错误错误经历曾将return放在if块之外导致函数刚进入就直接结束无法进入下方的for循环。教训在 DFS 中return通常只出现在递归出口Base Case中代表当前路径搜索完毕。2. 回溯的必要性理解反思如果不写used[i] false数字被用过一次后就永远失效最终只能输出1 2 3 ... N这一种结果无法生成其他排列。