思想
在每次递归中,我们尝试将某个位置分成多个分支,将尚未确定的位置个数减少1,
从而转化为规模更小的子问题。
顺序 设N =9
- 依次枚举每个数放哪个位置(从1开始,1有9种选择,2有8种…)
- 依次枚举每个位置放哪个数(从第一个位置开始,有9种选择,第二个位置有8种)
变量初始化问题
全局变量初始化为0;
局部变量初始化是随机值;
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;
int n,st[N], path[N];
//st[i] 表示i的状态 0没有被选 1被选择
//下标从1开始
void dfs(int u)
{
if(u>n)
{
for(int i=1;i<=n;i++)
{
printf("%d ", path[i]);
}
puts("");
return ;
}
// 依次枚举每个分支,当前位置可以填那些数
for(int i=1;i<=n;i++)
{
if(st[i]==0) //当前位置的i分支这个数 0没被使用
{
st[i] = 1; //选择此分支 标记这个数字
path[u] = i;
dfs(u+1);
st[i] =0;
}
}
}
int main()
{
scanf("%d", &n);
dfs(1);
return 0;
}