【理论基础】

• 什么是回溯算法？

  • 回溯函数其实也就是递归函数，回溯算法都是用递归函数实现的，是一种纯暴力的搜索方式，本质是穷举出所有的可能，然后选出符合条件的结果集。

卡哥给我们提供了一个回溯算法的模板，在做题的过程中发现，这个模板确实特别特别好用，几乎所有的回溯算法题目都可以用这个模板写出相应的递归函数：

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

对于回溯算法，有下文这几个主要的题目类型：

【组合问题】

个人感觉组合问题是相对基础的回溯算法问题类型，需要考虑的东西不算多，但是包含回溯算法特点的要素在组合问题里都有体现，因此，卡哥在这里给我们列举了k层for循环的例子，告诉我们为什么需要使用回溯算法———即该问题就算使用暴力搜索，也没办法控制for循环嵌套的次数，因此我们将for循环写进递归函数里，由递归函数帮我们实现控制for循环嵌套次数的动作，同时我们又需要遍历所有可能，所以用回溯来不断调整结果集。

在组合总和II这道题目中，我们需要对集合中的元素区中，卡哥当时自创了两个词，即树枝去重和树层去重

回溯算法还有一个重要的提高效率步骤，就是剪枝，即将根本不可能符合条件的“无效遍历”部分用if语句跳过，减少for循环的遍历次数，这个剪枝在某些特定题目里特别有效。

【切割问题】

其实我将切割问题也理解成组合问题，但是需要加入特殊的判断条件。例如分割回文串这题，卡哥给我们列出了几个难点：

• 切割问题其实类似组合问题
• 如何模拟那些切割线
• 切割问题中递归如何终止
• 在递归循环中如何截取子串
• 如何判断回文

切割问题还需要注意，在当前切割过的地方不能重复切割，因此递归函数需要传入的是i+2.

【子集问题】

组合问题关注的是我们符合条件的叶子节点，而子集问题更关注我们路径上的每一个符合条件的结点的收集。

因此，组合问题的终止条件我们一般可以不加，因为每一次递归都需要+1。

【排列问题】

排列问题与组合问题最大的区别是：排列问题注重排序，而组合问题不关注排序。

因此排列问题的每层搜索都是从0开始，而不是startIndex，但是排列问题需要uesd数组来记录path里面都放了哪些元素。

最后做了一下今天安排的三道选做hard题，我去。。。。重新安排行程这题我题目都看不懂。。题解更是看不懂。。。其它的两题其实还好，就是数独那题因为嵌套的for循环有点儿多，因此很容易不小心就忘记返回值了或者括号少了，N皇后就还好。