回溯法

什么是回溯法

回溯法是一种搜索算法，用于解决一些搜索问题。回溯的本质是穷举。

只要有递归就会有回溯。

回溯法并不高效，可惜有些问题只能用回溯法解决。类似：

1. 组合问题：N个数里面按一定规则找出k个数的集合
2. 切割问题：一个字符串按一定规则有几种切割方式
3. 子集问题：一个N个数的集合里有多少符合条件的子集
4. 排列问题：N个数按一定规则全排列，有几种排列方式
5. 棋盘问题：N皇后，解数独等等

回溯法解决的问题都可以抽象为树形结构，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归有终止条件，所以必然是一棵高度有限的树（N叉树）。