好久不学算法 发现dfs掌握的一点都不扎实。。
没吃早饭 饿了
#include <iostream>
using namespace std;
/*
DFS 每一层枚举一位
写DFS的步骤:
1. 判断终止条件
2. 做一些操作
3. 往下一层走
4. 恢复现场
*/
const int N = 10;
int num[N] = {0}; // 表示数字
bool visited[N] = {false}; // visited[i]表示数字i用过了没有
int n = 0; // 总共有几位
void dfs(int pos) {
// pos: 哪一位
if (pos == n) {
// 完成了一条路径 打印出来
for (int i = 0; i < n; i ++) cout << num[i] << " ";
cout << "\n";
return; // 终止条件
}
// 不终止的话 我们尝试在这一位上填所有可能的数字
for (int i = 1; i < n + 1; i ++) {
if (!visited[i]) {
num[pos] = i; // 这一位可以填i
visited[i] = true; // 后面遍历的时候 就不能填了
dfs(pos + 1); // 下一层
visited[i] = false; // 恢复现场
}
}
}
int main() {
cin >> n;
dfs(0);
return 0;
}