回溯算法理论基础.md

回溯

• 回溯是递归的副产品，只要有递归就会有回溯
• 回溯并不是一种高效的算法，因为回溯的本质是穷举，也就是暴力算法
• 有些问题只能用靠回溯法暴力解决
• 回溯法解决的问题都可以抽象为树形结构（N叉树）

回溯可以解决的问题

• 组合问题
• 切割问题
• 子集问题
• 排列问题
• 棋盘问题

回溯三部曲

1. 回溯函数模板返回值以及参数
   1. 返回值一般为void
   2. 先写逻辑，然后需要什么参数，就填什么参数
2. 回溯函数终止条件
3. 回溯搜索的遍历过程
   1. for循环：横向遍历
   2. backtracking（递归）：纵向遍历

模板

func backtracking(参数) {
    if (终止条件) {
        存放结果
        return
    }
	
    for (选择：本层集合中元素（树中结点孩子的数量就是集合的大小) {
        处理结点
        backtracking(路径，选择列表) // 递归
        回溯，撤销处理结果
    }
}