前言例题
题目描述输入输出样例输入样例输出数据范围限制 分析代码
前言
这是一道非常经典的深度优先搜索题。
例题
1148 全排列 (Standard IO)
题目描述
给定N(N<10)，按照字典序输出所有的N排列。
输入
第一行输入N。
输出
输出1到N的全排列，一行一个排列，按照字典序顺序输出。
样例输入
3
样例输出
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
数据范围限制
N<10
分析
分别以1-n为开头，一层层递推，如果n个数都用过了，就输出这一组解，然后返回。
代码
#include<bits/stdc++.h>
using namespace std;
int a[
15],n,b[
15];
void dfs(
int step,
int s)
{
if(step==n)
{
for(
int i=
1;i<=n;i++)
{
cout<<a[i]<<
' ';
}
cout<<endl;
}
for(
int i=
1;i<=n;i++)
{
if(b[i]==
0)
{
a[s]=i;
b[i]=
1;
dfs(step+
1,s+
1);
b[i]=
0;
}
}
return;
}
int main()
{
cin>>n;
dfs(
0,
1);
}
