企业官网建设流程全解析

记录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. 问题转化（排列树模型）：
   生成 1∼n 的全排列，本质上是在构建一棵深度为 nn 的“排列树”。我们在树的每一层（对应排列中的每一个位置），从 1∼n中选择一个还没有被使用过的数字填入。

2. 算法设计（DFS + 状态标记）：

   • 使用一个数组path来记录当前正在构建的排列序列。
   • 使用一个布尔数组vis来记录哪些数字已经被用过了（避免重复）。
   • 每次递归时，枚举 1∼n 的所有数字。如果某个数字没有被用过，就把它放入path中，标记为已用，然后进入下一层递归。
   • 当递归深度达到 n 时，说明一个完整的排列已经生成，将其输出。
   • 回溯的关键：从下一层递归返回后，必须将刚才标记为已用的数字重新标记为未用（vis[i] = 0），以便在后续的循环中尝试其他数字。

代码分块详细解释

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

核心逻辑总结表