啊哈算法 不撞南墙不回头——深度优先遍历 输出1~n的全排列

输入一个数n，输出1~n的全排列

程序如下：

// dfs23.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>

using namespace std;

int a[10];
int book[10];//为赋值，默认为0
int n;

//step表示站在第n+1个盒子面前，表示前n个盒子已经放好扑克牌
void dfs(int step)
{
	int i;
	if (step == n + 1)
	{
		//输出一种排列(1~n号盒子中扑克牌编号)
		for (i = 1; i <= n; i++)
		{
			cout << a[i];
		}
		cout << endl;
		return;
	}
	//此时站在第step个盒子面前，应该放那张牌呢？
	//按照1，2，3，.......n的顺序一个个的尝试
	for (i = 1; i <= n; i++)
	{
		//判断扑克牌i是否还在手上
		if (book[i] == 0)//book[i]表示i号扑克牌在手上
		{
			//开始尝试使用扑克牌i
			a[step] = i;//将i号扑克牌放入到第step个盒子中
			book[i] = 1;//将book[i]设为1，表示i号扑克牌已经不在手上
			dfs(step + 1);//函数递归  
			book[i] = 0;//这步非常重要，一定将刚才尝试的扑克牌收回，
			//才能进行下一次尝试
		}
	}
	return;
}


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

***/

int _tmain(int argc, _TCHAR* argv[])
{
	cin >> n;
	dfs(1);

	system("pause");
	return 0;
}