目录

回溯算法笔记

通俗的讲,回溯法约等于递归里面嵌套for循环

回溯法问题类型

  1. 组合类
    • 数组子数列
  2. 切割类
    • 回文子串
  3. 子集类
    • 类似组合
  4. 排列类
    • 有序的组合
  5. 棋盘类
    • n皇后

问题解决思路

将回溯问题抽象为一棵n叉树,水平方向(广度)的循环使用for循环来解决,垂直方向(深度)的循环使用递归来解决

./1.jpg

伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void backTracking(args){
	if(termination)//终止条件
	collect result;//收集结果
	return result;//返回结果
}
for(each item in Set){//集合元素
	processing node;//处理节点
	recurrence function;//递归函数
	backTrack operation;//回溯操作
}
return final result;//返回最终结果

回溯法基本步骤

  1. 递归参数返回值
  2. 确定终止条件
  3. 单层递归逻辑