题目描述
blablabla
样例
#include<iostream>
using namespace std;
const int N =1E5+10;
bool st[N];// 保存状态
int array[N]; // 数组
int n;
void dfs(int x)
{
if(x>n)
{
for(int i=1;i<=n;i++) printf("%d ",array[i]);
puts("");
return ;
}
for(int i=1;i<=n;i++) // 每个x 1,2,3都会经历一个for循环
{
if(!st[i]) // 表示该数字没有被用过
{
st[i] = true;
array[x] = i;
dfs(x+1);
array[x] = 0;
st[i] = false;
}
}
}
/*
eg: 1 2 3
1。x = 1 >>> for(int i=1) st[1] = false >>> array[x] = i >>>x=2
2. x = 2 >>> for(int i=1) st[1]=true for(int i=2) st[2] = false >>>> array[x]=i,st[i] = true >>>x = 3
3. x = 3 >>> for(int i=1) st[1] = true i =2 str[2] = true >>>i=3 st[3]=false array[x] = i, >>>> x=4
4 x = 4 >>> x>3 printf(array[i);
回溯
1 x = 3 i = 3 st[i] = false array[x] = 0
2 x = 2 i = 2 st[i] = false array[x] = 0 ----- i=3 --i=1 true i=2 flase array[2]=3, st[3] = true------dfs(3)
i = 1 true i = 2 flase ------ st[i] = true array[3] = i ----x = 4 printf(1 3 2)
i++ i=4 return; x = 3 st[i] = false array[3] = 0,---- x = 2 st[i] = false array[2]=0,i++ i=4 retrun;
------
3 x = 1 st[1] = false array[1] = 0, i++ i=2 ..........
*/
int main(void)
{
cin>>n;
dfs(1);
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla