32 lines
1.0 KiB
C++
32 lines
1.0 KiB
C++
// dfs模版
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
const int N = 1e2 + 10; // 定义最大数组大小
|
||
int a[N]; // 存储排列结果
|
||
bool vis[N]; // 标记数字是否被访问过
|
||
int n; // 排列的大小
|
||
|
||
// 回溯函数，dep表示当前处理到第几个数字
|
||
void dfs(int dep) {
|
||
if (dep == n + 1) { // 如果已经处理完所有数字
|
||
for (int i = 1; i <= n; i++) { // 输出排列
|
||
cout << a[i] << " \n"[i==n];
|
||
}
|
||
return;
|
||
}
|
||
|
||
for (int i = 1; i <= n; i++) { // 尝试将1到n的每个数字放入当前位置
|
||
if (vis[i]) continue; // 如果该数字已经被使用，跳过
|
||
vis[i] = true; // 标记该数字为已使用
|
||
a[dep] = i; // 将数字放入当前位置
|
||
dfs(dep + 1); // 递归处理下一个位置
|
||
vis[i] = false; // 回溯，恢复状态
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
cin >> n; // 输入排列的大小
|
||
dfs(1); // 从第一个位置开始递归
|
||
return 0;
|
||
} |