给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式
共一行,包含一个整数 n。
输出格式
按字典序输出所有排列方案,每个方案占一行。
数据范围
1\le n\le 7
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
时间复杂度
O(n\cdot n!)
核心思想
path
数组保存排列,当排列的长度为 n 时,是一种方案,输出。st
数组表示数字是否用过。当st[i]
为 true 时:i 表示已用,否则未用。dfs(i)
表示的含义是:在 path[i]
处填写数字,然后递归的在下一个位置填写数字。核心函数
void dfs(int u){
if(u == n)
{
for(int i = 0; i < n; i ++ )
cout << path[i] << ' ';
cout << endl;
return;
}
else
{
for(int i = 1; i <= n; i ++ )
{
if(!st[i])
{
path[u] = i;
st[i] = 1;
dfs(u + 1);
st[i] = 0; // 回溯
}
}
}
}
代码实现
#include <iostream>
using namespace std;
const int N = 10;
int n, path[N];
bool st[N];
void dfs(int u){
if(u == n)
{
for(int i = 0; i < n; i ++ )
cout << path[i] << ' ';
cout << endl;
return;
}
else
{
for(int i = 1; i <= n; i ++ )
{
if(!st[i])
{
path[u] = i;
st[i] = 1;
dfs(u + 1);
st[i] = 0;
}
}
}
}
int main (){
cin >> n;
dfs(0);
return 0;
}