一、回溯算法理论基础
学习:
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
- 初步了解了回溯,以及最简单的回溯算法和剪枝