详细题解，保你AC

代码结构解析

#include <bits/stdc++.h>
using namespace std;

int n;               // 输入的整数n，表示要生成1~n的全排列
int a[10];           // 存储当前正在构建的排列（最多9个元素，符合n≤9的约束）
bool vis[10];        // 标记数字是否已被使用（vis[i]=true表示数字i已在当前排列中）

// 深度优先搜索函数：u表示当前正在填充排列的第u个位置（从0开始）
void dfs(int u) {
    // 递归终止条件：当排列长度等于n时，输出当前排列
    if (u == n) {
        for (int i = 0; i < n; i++) {
            printf("%5d", a[i]);  // 每个数字占5个场宽（格式要求）
        }
        printf("\n");
        return;
    }

    // 遍历1~n的所有数字，尝试加入当前排列
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {  // 如果数字i未被使用
            a[u] = i;       // 将i放入当前排列的第u个位置
            vis[i] = true;  // 标记i为已使用（避免重复）
            dfs(u + 1);     // 递归处理下一个位置（u+1）
            vis[i] = false; // 回溯：取消i的标记，允许其他分支使用i
        }
    }
}

int main() {
    cin >> n;   // 输入n
    dfs(0);     // 从排列的第0个位置开始递归
    return 0;
}

核心逻辑详解

1.变量作用：

• n：输入的整数，确定排列的范围(1 ~ n)。
• a[10]：存储当前正在构建的排列，例如a = [1,3,2]表示排列 “1 3 2”。
• vis[10]：布尔数组，vis[i] = true表示数字i已被选入当前排列，避免重复使用。

2.变量作用：

• 终止条件：当u == n时，说明已经选完了 n 个数字（排列长度为 n），此时输出当前排列a。

• 递归逻辑：
  遍历数字i从 1 到 n（按顺序遍历，保证字典序）。
  若i未被使用（!vis[i]），则将i放入当前排列的第u位（a[u] = i），并标记i为已使用（vis[i] = true）。
  递归调用dfs(u+1)，处理下一个位置（构建排列的下一位）。
  回溯：递归返回后，将vis[i]重置为false，表示i可以被其他排列使用（例如生成 “1 2 3” 后，释放 3，再生成 “1 3 2”）。

3.字典序保证：

• 由于在for循环中按i=1,2,...,n的顺序遍历数字，优先选择较小的数字填入当前位置，因此生成的排列自然按字典序排列。
• 例如 n=3 时，先填 1，再填 2，最后填 3（生成 “1 2 3”）；之后回溯释放 3，尝试填 3 再填 2（生成 “1 3 2”），以此类推。

4.格式输出：

• 使用printf("%5d", a[i])控制每个数字占 5 个字符宽度（不足的用空格填充），与样例输出一致。

示例运行过程（n=3）

1.初始调用dfs(0)，开始构建排列的第 0 位。
2.第一次循环i=1（未使用），a[0]=1，vis[1]=true，调用dfs(1)。
3.dfs(1)中，循环i=2（未使用），a[1]=2，vis[2]=true，调用dfs(2)。
4.dfs(2)中，循环i=3（未使用），a[2]=3，vis[3]=true，调用dfs(3)。
5.dfs(3)中u=3 == n=3，输出 “1 2 3”。
6.回溯：vis[3]=false → 返回dfs(2) → 循环结束 → vis[2]=false → 返回dfs(1)。
7.dfs(1)中继续循环i=3，生成 “1 3 2”，以此类推，直到所有排列生成完毕。

总结

这段代码通过 DFS 的 “选择 - 标记 - 递归 - 回溯” 流程，高效生成了 1~n 的所有全排列，并通过按顺序遍历数字保证了字典序，同时满足了输出格式要求。对于 $n≤9$ 的情况，效率完全足够。

---

源代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int a[10];  
bool vis[10];  
void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i++) {
            printf("%5d", a[i]); 
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) { 
            a[u] = i;
            vis[i] = 1;
            dfs(u + 1);    
            vis[i] = 0;
        }
    }
}
int main() {
    cin >> n;
    dfs(0); 
    return 0;
}

感谢豆包的支持