基本思路
枚举序列中的每一个位置,填入之前未出现的数字
为什么能用dfs
前一个位置的选择会对后面位置的选择产生影响,每一次选择本质上创建了一条树的分支,最终的叶结点表示所有位置枚举完毕,即结果序列,因此可以用dfs遍历整棵树,在叶结点处输出结果
为什么要恢复现场
因为状态判断数组是一个全局数组,如果一个分支修改了状态,那么就会影响另外一个分支的状态判断,比如,一个分支走到了叶结点,即所有位置都填了数,那么st中所有元素都为true,显然,在这之后的分支就无法继续了
#include <iostream>
using namespace std;
const int N = 10;
int path[N];
bool st[N];//状态数组,st[i] = true 表示i在之前出现过
int n;
void dfs(int u)
{
if (u == n) //u表示的是当前所在的位置
{
for (int i = 0; i < n; i++) printf("%d ", path[i]);
puts("");
return;
}
else
{
for (int i = 1; i <= n; i++)
{
if (!st[i]) //当前数在之前未出现,则填入当前位置,并标记为已出现
{
path[u] = i;
st[i] = true;
dfs(u+1);
path[u] = 0;
st[i] = false;
}
}
}
}
int main()
{
scanf("%d", &n);
dfs(0);
return 0;
}
位运算优化之后为什么不要恢复现场了
相当于将状态判断数组变成一个局部数组,各个分支直接互不干扰
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int path[N];
int n;
void dfs(int u, int state)
{
if (u == n)
{
for (int i = 0; i < n; i ++ )
printf("%d ", path[i]);
puts("");
return;
}
for (int i = 0; i < n; i ++ )
{
if (!(state >> i & 1))
{
path[u] = i + 1;
dfs(u + 1, state + (1 << i)); //一定要加括号,移位操作优先级比加减低
}
}
}
int main()
{
cin >> n;
dfs(0, 0);
return 0;
}