回溯法初步

本文为参考公众号所做的笔记。
代码随想录原文

回溯法本质是穷举，穷举所有可能，然后选出我们想要的答案，所以它并不是一个高效的算法。但是由于有些问题本身能用暴力搜出来就不错了，所以回溯法也有很多的应用。
回溯法解决的问题
1、组合问题：N个数里面按一定规则找出k个数的集合
2、排列问题：N个数按一定规则全排列，有几种排列方式
3、切割问题：一个字符串按一定规则有几种切割方式
4、子集问题：一个N个数的集合里有多少符合条件的子集
5、棋盘问题：N皇后，解数独
组合与排列区别：
组合是不强调元素顺序的，排列是强调元素顺序的。
回溯法的理解
回溯法的解空间是一个树，回溯法解决的是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成了树的深度。

回溯法模板

1、回溯函数返回值以及参数
返回值一般为空。
一般先写逻辑，然后需要什么参数就填什么参数

void backtracking(参数)

2、回溯函数终止条件
一般来说搜索到树的叶子结点，就是找到了满足条件的一个答案，把这个答案存放起来，并结束本层递归。

if(终止条件)
{
	存放结果;
	return;
}

3、回溯搜索的遍历过程
集合的大小构成了树的宽度
递归的深度构成了输的深度
集合大小和孩子的数量是相等的

回溯函数遍历过程的伪代码如下：

for(选择：本层集合中的元素（树中结点孩子的数量就是集合的大小）)
{
	处理结点;
	backtracking(路径,选择列表);		//递归
	回溯,撤销处理结果
}

for循环就是遍历集合区间，可以理解一个结点有多少个孩子，这个for循环就执行多少次。
for循环就是横向遍历，backtracking就是纵向遍历。
整个模板如下：

void backtracking(参数)
{
	if(终止条件)
	{
		存放结果;
		return;
	}
	for(选择：本层集合中元素(树中结点孩子的数量就是集合的大小))
	{
		处理结点;
		backtracking(路径,选择列表);		//递归
		回溯，撤销处理结果;
	}
}