1.全排列-（DFS）

全排列问题 - 洛谷

---

DFS（深度优先搜索 depth first search） 

定义：深度优先搜索，是搜索算法的一种，在深度优先遍历的时候，已经知道他的遍历顺序，从某一个结点出发，选择与他连接的任一孩子，然后开始遍历，一直到最底部的叶子结点，（一条路走到黑），然后开始回溯，回溯到上一层如果还有分支，继续深入，直到遍历完所有的结点。

特点：深搜类似于盲目的搜索，在回溯的过程中，会返回上一状态，是由递归实现的，复习递归函数，联想俄罗斯套娃，最里面的套娃的头部是最后进去的，但是脚是先出来的，所以符合先进后出的特点，类似于栈。深搜的空间复杂度较小，因为只存储了从初始状态到目标状态的一条搜索路径，但是如果要得到最优解，需要遍历整个搜索树（也就是需要判断所有可以发生的情况），时间复杂度较高。

算法框架：

    

---

回溯算法： 

定义：回溯法，也称为试探法，它是从问题的某一状态出发，不断试探的往前走一步，当一条路走到终点的时候，不能再前进，这个时候要倒退一步或者若干步，从另一种可能的状态，继续搜索，直到所有的路径都搜索完毕。

特点：深度优先搜素求解时，当找到了目标状态后，还要回头寻找初始状态到目标状态的路径，而回溯算法不同，当找到目标状态后，搜索的路径就是一条从初始状态到目标状态的解路径，这里稍微有点难理解，就是当已经无法再深入了，得到了一条路径，整个路径上的现场都会被保存下来，我们只要在递归出口收集结果即可。

回溯法与DFS的联系：

（1）DFS包含回溯法，回溯法是对DFS的一种改进，更为实用

（2）DFS是需要控制整个搜索路径如何转移，回溯法就是对DFS的一种控制策略

（3）回溯法不需要记录整棵搜索树，只需要记录从初始状态到当前状态的搜索路径，占用空间少

题型：

排列问题，组合问题，切割问题，棋盘问题等

算法框架：

  

---

解题思路：

（1）此题为排列问题，利用回溯法来实现。首先一共有n个数，如果我们要求n个数排列顺序都实现的话，只需要依次for循环嵌套即可。例如当求1,2,3的全排列，可以这么实现

  

 （2）当数字n较小时，我们可以利用循环嵌套的方式，那么当n越大，嵌套的层数也就越多，时间复杂度为O（n^n），当n=15的时候，就已经超时了，（弱弱打个表，也不是不行）。

（3）那么如何让他不那么复杂，变的优美一点呢？发现循环套循环，不就类似于递归函数一层套一层么？符合先进后出的特点，所以利用DFS和回溯来实现。

（4）如果使用递归，那么就要找到出口，出口在哪里呢？可以建立一个数组ans【】，依次将每层可以取的数字按序放入ans数组中，当存放的数字个数为n的时候，便可以结束了。

（5）那么如何标记已经被使用过的数字呢？可以建立一个bool数组vis【】，利用下标打标记的方法，如果这个下标数字的元素值为0的时候，证明没有被使用过，所以可以用，这也就是算法框架中的第i种状态可行，如果可行的话，需要保存现场，也就是记录一下，当前数字已经备用了，将此时的下标数字对应的元素值打上标记，并将这个数字存放到ans数组中，继续下一层。

（6）直到无法继续深入下去后，那么就该回头了，也就是恢复现场，恢复现场干了一件什么事呢？最后一层这个数字是被用过了，所以标记被用过，当最后一层这个数字已经回溯了，说明又可以用了，所以标记还可以用。

配合下列图示，理解解题思路：

（1）当从1开始枚举百位的数字的时候，第一层1是可以用的，然后深进入第二层，1不能再用，所以用了2，接着进入第三层，1和2都被用过了，只能用3，需要形成的数字是123，当到达第3层的时候无法再深入，那么取消3的标记，回溯到第二层，此时第二层循环中的j++，变为了3，也就是十位上数字是3，继续下一层，1和3都被用过，此时只能用2，所以形成了数字132

（2）此时回到了第一层，很多人不明白为什么直接回到第一层，因为在第二层和第三层的j和k都已经枚举完，所以回到了最外层的循环，开始枚举i=2的情况，然后继续步骤1.

---

#include
using namespace std;
 
int ans[15];//用来存放排列的数字 
bool vis[15];//标记数组用来记录哪些数字没有用过 
 
int n;
void dfs(int x)
{
	if(x>n)//当数字超过n的时候，执行打印功能 
	{
		for(int i=1;i<=n;i++)
		printf("%5d",ans[i]);
		cout<
        return;
	}
	
	for(int i=1;i<=n;i++)//依次枚举1-n个数 
	{
		if(vis[i]==0)//如果当前数字没有被用过 
		{
			vis[i]=1;//标记该数字开始用了 
			ans[x]=i;//将该数字放入到ans数组的下标1位置 
			dfs(x+1);//继续深搜 
			vis[i]=0;//当最里层的递归执行完后，取消该数字标记（回溯） 
		}
	}
}
int main()
{
	cin>>n;
	dfs(1);//从数字1开始深搜递归 
	return 0;
}

---

现在稍微变一下题目，如果是从n个数中挑选m个数进行全排列呢？应该如何实现?

解题思路：

如果还是按照递归的思路来想，想这道题的出口是什么？dfs（x）函数中的x是表示取的数量，那么当x>m的时候，就已经可以结束递归了，意思为我只要这么多，可以进行回溯了！

代码实现：

#include
using namespace std;
 
int ans[15];//用来存放排列的数字 
bool vis[15];//标记数组用来记录哪些数字没有用过 
 
int n,m,cnt;
void dfs(int x)
{
	if(x>m)//当数字超过m的时候，执行打印功能 
	{
		for(int i=1;i<=m;i++)
		printf("%5d",ans[i]);
 
		cnt++;//计数器增加
		cout<
 
        return;
	}
	
	for(int i=1;i<=n;i++)//依次枚举1-n个数 
	{
		if(vis[i]==0)//如果当前数字没有被用过 
		{
			vis[i]=1;//标记该数字开始用了 
			ans[x]=i;//将该数字放入到ans数组的下标1位置 
			dfs(x+1);//继续深搜 
			vis[i]=0;//当最里层的递归执行完后，取消该数字标记（回溯） 
		}
	}
}
int main()
{
	cin>>n>>m;
	dfs(1);//从数字1开始深搜递归 
 
	cout<//输出全排列的数量
	return 0;
}