题目描述
把 1~n 这 n 个整数排成一行后随机打乱顺序,输出所有可能的次序。
输入格式
一个整数n。
输出格式
按照从小到大的顺序输出所有方案,每行1个。
首先,同一行相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。
数据范围
1≤n≤9
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
算法1
(dfs) $O(n^2)$
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std ;
const int N = 10 ;
int path[N] ;
int n ;
bool st[10] ;
void dfs ( int x ) {
if ( x == n ) {
for ( int i = 0 ; i < n ; i ++ ) cout << path[i] << ' ' ;
cout << endl ;
return ;
}
for ( int i = 1 ; i <= n ; i ++ ) {
if ( st[i] == false ) {
st[i] = true ;
path[x] = i ;
dfs ( x + 1 ) ;
st[i] = false ;
}
}
}
int main ( ) {
cin >> n ;
dfs ( 0 ) ;
return 0 ;
}