回溯算法笔记
目录
通俗的讲,回溯法约等于递归里面嵌套for循环
回溯法问题类型
- 组合类
- 数组子数列
- 切割类
- 回文子串
- 子集类
- 类似组合
- 排列类
- 有序的组合
- 棋盘类
- n皇后
问题解决思路
将回溯问题抽象为一棵n叉树,水平方向(广度)的循环使用for循环来解决,垂直方向(深度)的循环使用递归来解决
伪代码
|
|
回溯法基本步骤
- 递归参数返回值
- 确定终止条件
- 单层递归逻辑