P1706 全排列问题

记录159

#include<bits/stdc++.h>
using namespace std;
int path[15];
bool vis[15];
int n;
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;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
dfs(1);
return 0;
}

题目传送门https://www.luogu.com.cn/problem/P1706

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

 核心解题思路

这道题是一道非常经典的深度优先搜索（DFS）与回溯算法入门题。

代码分块详细解释

1. 全局变量定义

#include<bits/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 顺序枚举数字的，所以生成的排列天然就是字典序的。

核心逻辑总结表