一、回溯算法理论基础
学习：
1. 基本概念
回溯法是一种搜索方式
回溯的本质是穷举，是递归的副产品，即回溯算法就是递归算法
回溯解决的问题都能理解成树形结构，一般是在集合中递归查找子集。集合的大小构成树的宽度(n叉树)，递归的深度构成了树的深度
2. 回溯解决的问题
(1)组合问题：N个数里面按一定规则找出k个数的集合
(2)切割问题：一个字符串按一定规则有几种切割方式
(3)子集问题：一个N个数的集合里有多少符合条件的子集
(4)排列问题：N个数按一定规则全排列，有几种排列方式
(5)棋盘问题：N皇后，解数独等等
3. 构建回溯算法模板（可比对递归）
- 函数返回值以及参数
- 终止条件
- 单次循环内容
二、77. 组合
题目链接：
LeetCode 77. 组合
学习前：
思路：
- 函数返回值以及参数：void fun(int n, int k, int start)，其中start是for循环开始的数值
- 终止条件：当list的长度与k相等，则将其加入结果集res中，注意是深拷贝
- 单次遍历内容：从start到n依次添加值到list中，然后递归调用fun(n,k,start+1)
学习后：
进一步优化。对于单次遍历内容，for循环里面的循环判断条件从i<=n优化为i<=(n-k)+1，即当剩余的数字已经不足以满足集合的长度时，无需再遍历
三、学习总结
- 时间：1.5h
- 初步了解了回溯，以及最简单的回溯算法和剪枝