题目描述
给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式
共一行,包含一个整数 n。
输出格式
按字典序输出所有排列方案,每个方案占一行。
数据范围
1≤n≤7
样例
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
算法1
C++ 代码
#include <iostream>
using namespace std;
const int N = 10;
int n;
int visited[N],path[N];
void dfs(int index) // index 表示当前要放的位置
{
if(index == n)
{
for(int i = 0; i < n; i ++) cout << path[i] << ' ';
cout << endl;
return;
}
for(int i = 1; i <= n; i ++ )
{
if(!visited[i])
{
path[index] = i;
visited[i] = 1;
dfs(index+1);
/*回溯,就以第一个排列完成说起:1 2 3
放完 3 后,此时 i = 3, 当上一个 dfs 里此处的 i = 2;
2 执行完了 ++ 变为 3 就是考虑倒数第二个位置是否放 3;
而 visited 是贯穿全局的,因此需要回溯将 visited[3] = 0
*/
visited[i] = 0;
//此处 path 虽然也贯穿全局 但由于 index 相同会覆盖上一个,
//但如果前面用 vector 中的 push 的话,覆盖不了,需要 pop
}
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla