DFS输出全排列

前言

输入n(1 <= n <= 20),按字典序输出所有1~n的排列。如果排列数量太多，则只需要输出前100个

输入样例

3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路

这是一道很简单的搜索算法题。

总体思路是：

（1）假如我们先确定第一个位置要填的数，然后才能选下一个位置要填的数。那么由于每个位置都有多个数可填，所以最终所有位置的选择过程其实是一颗树。我们称他为搜索树。

如下图所示，每一层其实就是确定一个位置。最终答案都是在树的叶子上。

（2）我们只需使用搜索算法对这棵树进行搜索即可。在这里我用的是深度优先搜索算法（DFS）。

（3）值得注意的是：这道题要求按照字典序从小到大输出。所以对于每个位置，从小到大填即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int p[1000];//存储当前排列情况
bool vis[1000];//标记数组

//决定第step个位置的数值
void dfs(int step)//author's blog == https://www.cnblogs.com/toulanboy/
{
	if(cnt>=100)//假如排列数超出了100，那就行了
		return ;
	if(step==n&&cnt<100)//如果前面n个数都填好了，说明当前可以输出一个情况了
	{
		cnt++;
		for(int i=0;i<n;i++)
		cout<<p[i]<<" ";
		cout<<endl;
		return ;
		
	}
	for(int j=1;j<=n;j++)
	{
		if(vis[j]==0)//如果第j个数值没有被用，那就填这个数
		{
			p[step]=j;
			vis[j]=1;
			dfs(step+1);//继续填下一个数
			vis[j]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(0);
	return 0;
}