c++ 递归算法求全排列

全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列

eg:{1，2，3}，则123，132，213，231，312，321为它的全排列

思路：二叉树，深度优先搜索（dfs);

说人话就是：

假如是1-3的全排列 首先 遍历第一个位置 为1，第二个位置为2，第三个位置为3，排满后1 2 3；

再将第三个位置清空1 2 * ；

此时第三个位置不能为4（因为1-3最大为3）所以不填继续清空第二个位置1 * *；

此时第二个位置可以为3，第三个位置可以为2

排后 1 3 2；

代码实现：

#include
using namespace std;

//输出n的全排列
int n;

//数组大小
const int len = 11;

//将排列顺序存入数组a中
int a[len];

//判断数组a中有无此元素 初始化为false 表示a无此元素
bool hashTable[len] = {false} ;

//全排列函数
void test(int index)//index表示位置 默认从第一个位置开始
{
	//防御性编程 判断是否越界
	if (index == n + 1)
	{
		for (int i = 1; i <= n; i++)
		{
			cout << a[i] << ' ';
		}
		cout << endl;
		return;
	}

	//遍历每个位置的可能出现的数据 i为这个位置上的数
	for (int i = 1; i <= n; i++)
	{
		if (hashTable[i] == false)//判断当前排列中有无此元素
		{
			a[index] = i;		 //第index位置为i,存入数组
			hashTable[i] = true; //若没有则放入并且hashtable为真
			test(index + 1);	 //往下一个位置插入元素 注意数组下标可能越界
			hashTable[i] = false;
			//“回溯”<=> 最后一个位置插入后 再从后向前清空该位置的数据并且替换
			//比如 123 回溯后变成 1** 此时有for循环再次插入值 变为 132 
		}
	}
}

int main()
{
	cin >> n;
	//从第一个位置开始插入数据遍历
	test(1);

	return 0;
}

结果展示：