DFS入门题目
传送门
题目描述 Description
给出一个n, 请输出n的所有全排列
输入描述 Input Description
读入仅一个整数n (1<=n<=10)
输出描述 Output Description
一共n!行，每行n个用空格隔开的数，表示n的一个全排列。并且按全排列的字典序输出。
样例输入 Sample Input
3
样例输出 Sample Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
分析：
这个题目用next_permutation(p,p+n)会TLE，得用搜索。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
using namespace std;
int n;
bool vis[15];
int p[15];
void (int x){
if(x>=n+1){
for(int i=0;i<n;i++)
cout<<p[i]<<" ";
cout<<endl;
return ;
}
for(int i=1;i<=n;i++)
if(!vis[i]){
p[x]=i;
vis[i]=true;
DFS(x+1);
vis[i]=false;
}
return ;
}
int main(){
cin>>n;
DFS(1);
return 0;
}
|
近期评论