全排列问题
题目描述
按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列,即 $n$ 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 $n$。
输出格式
由 $1 \sim n$ 组成的所有不重复的数字序列,每行一个序列。
每个数字保留 $5$ 个场宽。
样例 #1
样例输入 #1
3
样例输出 #1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
提示
$1 \leq n \leq 9$。
dfs
#include<iostream>
using namespace std;
const int N = 9;
int n,path[N];
bool st[N];
void dfs(int u){
if(u==n){//搜出了一种方案输出
for (int i = 0; i < n; i ++ )cout<<" "<<path[i];
puts("");
return;
}
for (int i = 1; i <= n; i ++ ){
if(!st[i]){//回溯
path[u] = i;
st[i] = true;
dfs(u+1);
st[i] = false;
}
}
}
int main()
{
cin>>n;
dfs(0);
}