回溯算法

概述

• 回溯法也叫做回溯搜索法，它是一种搜索的方式

• 回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案

• 可以通过可行性剪枝和优化剪枝等操作，优化回溯法

解决问题

• 组合问题

• 排列问题

• 子集问题

• 切割问题

• 棋盘问题

总结来说，回溯法解决的问题一般设计多重循环

理解

• 回溯法解决的问题都可以抽象为树形结构

• 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

回溯法模板--回溯三部曲

• 参数和返回值

• 出口

• 回溯搜索的遍历过程

从代码中看出

• for循环可以理解是横向遍历-

• backtracking（递归）就是纵向遍历

• 这样就把这棵树全遍历完了