导引

如果我们想输出一个数的全排列，eg：1,2,3 的全排列
那么就有123,132,213,231,312,321，这六种。

那如何用代码实现呢？

for (int a = 1; a <= 3; a++)
{
	for (int b = 1; b <= 3; b++)
	{
		for(int c=1;c<=3;c++)
			if (a != b && a != c && b != c)
			{
				printf("%d%d%d", a, b, c);
			}
	}
}

暴力枚举是一种，但是如果数字编的更多呢？
如1,2，3,4,5,6,7,8,9呢？

如果我们还是一个一个枚举出来，别说计算机你也不愿意。

深度优化搜素（dfs）

它的基本形式是：

void dfs(int step)
	{
		//判断边界
		//尝试每一种可能
		for (int i = 1; i <= n; i++)
		{
			//继续下一步
			dfs(step+1)
		}
		//返回;
	}

再回到刚才的问题
给出了n个数（假设是三个）
那么我们可以看做，将三张牌放入三个盒子，一共有多少种不同的摆法；

首先我们定义一个数组来表示牌，一个数组来判断是否目前这个牌有没有在手上，
int book[10]，a[10]；
如果目前这个盒子没有牌
依次枚举下去，将手上的安装（先1，再2，后3）放入盒子

for (int i = 1; i <= n; i++)
{
	if (book[i] == 0)//此时牌在手上
	{
		a[step] = i;
		bool[i] = 1;
	}
}

接着，我们以相同的方法来处理下一个盒子（函数的递归调用）

void dfs(int step)
{
	for (int i = 1; i <= n; i++)
	{
		if (book[i] == 0)//此时牌在手上
		{
			a[step] = i;
			bool[i] = 1;
			dfs(step + 1)
		}
	}
	return；
}

这样，一轮下来，我们已经得到一个a数组，a[1]==1,a[2]==2,a[3]==3

这时候，我们依次退回上一个盒子，拿回刚才放进去的牌，

当退到第二个盒子拿回2的时候，我们手上现在就有了两张牌2,3.由于刚才

我们在第二个盒子放的是2，那么，我们根据上面所写的，（先1，再2，后3）这时，第二个盒子就一个放入3.第三个盒子放入2.

此时，我们又得到一个a数组，a[1]==1,a[2]==3,a[3]==2.

void dfs(int step)
{
	for (int i = 1; i <= n; i++)
	{
		if (book[i] == 0)//此时牌在手上
		{
			a[step] = i;
			book[i] = 1;
			dfs(step + 1);
			book[i] = 0;//将盒子的牌收回
		}
	}
	return；
}

我们依次将a数组打印出来，就得到他的全排序

完整代码如下

#include <stdio.h>
int a[10], book[10], n;
void dfs(int step)
{
	if (step == n + 1)
	{
		for (int i = 1; i <= n; i++)
		{
			printf("%d ", a[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (book[i] == 0)//此时牌在手上
		{
			a[step] = i;
			book[i] = 1;
			dfs(step + 1);
			book[i] = 0;//将盒子的牌收回
		}
	}
	return;
}
int main()
{
	scanf("%d", &n);
	dfs(1);//从第一个盒子开始
	return 0;
}