深度优先搜索---全排列

题目要求：

输入一个数n，输出1~n的全排列。比如，输入3，输出123、132、213、231、312、321。

解题思路：

用深度优先搜索，假设有n个盒子，从第一个盒子开始依次放直到放到最后一个盒子，期间用到递归调用。放到最后一个后，再依次返回，进行重新组合，其中还用到标记数组来判断是否被用过。

代码实现：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int a[10], book[10], n;void dfs(int step) {//step表示现在站在第几个盒子面前	int i;	if (step == n + 1) {//如果站在第n+1个盒子面前，表示前n个盒子已经放好了扑克牌		for (i = 1; i <= n; i++)			PRintf("%d", a[i]);		printf("/n");		return;//返回之前的一步，即最近一次调用dfs的地方	}	//此时站在第step个盒子面前应该放那张牌呢？按照1、2、3...n的顺序一一尝试	for (i = 1; i <= n; i++) {		//判断扑克牌i是否还在手上		if (book[i] == 0) {//表示第i号扑克牌在手上			//开始尝试使用扑克牌			a[step] = i;			book[i] = 1;//表示i号扑克牌已不在手上			//第step个盒子已经放好，接下来要走下一个盒子			dfs(step + 1);			book[i] = 0;//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试		}	}	return;}int main() {	scanf("%d", &n);	dfs(1);	system("pause");	return 0;}
实现效果：