题目描述
blablabla
DFS。最重要的是考虑其顺序,搜索顺序可以看作是一棵树。
我们使用一个path[]数组存储每个排列方案的排列顺序,使用一个st[]数组来标记1~n个数字的被访问情况。
若遍历数字i没有被访问过,即st[i]=false,则 path 数组第 u 个位置path[u]可以放数字i。而后搜索下一个位置u+1可以存放的数,直到搜索完所有位置为止。注意每完成一个排列方案都要恢复现场(回溯)。
以下为样例 n=3 的搜索流程:
样例
#include<iostream>
using namespace std;
const int N=10;
int n;
int path[N];
bool st[N]={false};//当前有没有用过
void dfs(int u)
{
if(u==n)//填满所有的空位
{
for(int i=0;i<n;i++) cin>>path[i];
return;
}
for(int i=1;i<=n;i++)
{
if(st[i]==false)
{
path[u]=i;
st[i]=true;
dfs(u+1);//递归到下一层
//递归后一句必须回溯/恢复现场
//path[u]=0;//会被不断覆盖掉,不需要恢复
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(0);
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla