题目描述
这道题可以用dfs解决,很入门。
样例
cin>>
3
cout<<
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
算法1
(dfs) $O(n^2)$
1.如果num = n+1了,说明这n位都放满了,所以就可以输出了。
2.将1~n这n个数字进行排列,不能重复。
3.如果i这个数字没有被用过。
4.第num位放入数字i。
5.由于i被使用过了,所以true。
6.处理下一位也就是第num+1位。
7.复原位是很重要的一步,将数字i进行false。
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 8;
int n, number[N];
bool ans[N];
void dfs(int num){
if(num == n + 1){
for(int i = 1; i <= n; i++)
cout << number[i] << " ";
puts("");
}
for(int i = 1; i <= n; i++)
if(!ans[i]){
number[num] = i;
ans[i] = true;
dfs(num + 1);
ans[i] = false;
}
}
int main(void){
cin >> n;
dfs(1);
return 0;
}
算法2
(STL) $O(n^2)$
利用dowhile循环和next_permutation(a,a+n)
来把这些组合输出,这是系统自带全排列函数
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int number[7];
int main(void){
int n;
cin >> n;
for(int i = 0; i < n; i++) number[i] = i + 1;
do{
for(int i = 0; i < n; i++) cout << number[i] << " ";
puts("");
}while(next_permutation(number, number + n)); //系统自带全排列函数
return 0;
}