知识点

1. 回溯算法

   1. 回溯算法解题思路：

      回溯算法的解决，其实就是一个决策树的遍历过程。

      只要明确3个问题即可：1、路径：即已经做出的选择；2、选择列表：当前可以进行的选择；3、结束条件：到达决策的底层，无法做出选择。

      在代码层面，就是一个for循环，遍历选择列表；for循环循环体中，使用递归调用，递归前做选择，递归后撤销选择。

2. DFS（深度优先遍历）

   1. DFS解题思路

      DFS其实就是回溯算法，直接使用回溯算法的解题技巧即可

LeetCode算法题

1. 求子集，求排列，求组合问题

   1. 解题思路：

      上述三种问题，都可以使用回溯算法（即DFS）解决

2. 解数独问题

   1. 解题思路：

      仍然是使用回溯算法解决

   2. LeetCode算法

      • 37.【解数独】

3. 括号问题

   1. 括号问题的种类

      括号问题一般分为两种类型：1、判断括号的合法性；2、合法括号的生成

   2. LeetCode算法题

      • 22.[括号生成]

        解题思路：

        组合问题都可以使用回溯算法来解决，其中的难点就是如何判断该组合的括号合法性。

        括号的合法性包含两个：1、一个合法括号组合的左括号数量一定等于右括号数量；2、一个合法括号组合P，必然对0<=i<=length(P)来说，子串P[0..i]中，左括号数量大于等于右括号