本篇文章是对leetcode tree和Top Interview Questions标签下7道backtracking类型题目的总结
Leetcode 46. Permuation
求一个数组的排列，不断加入新的元素递归，递归结束后删去，并在新一轮循环中同一个位置加入新的元素
Leetcode 22. Generate Parentheses
求（和）的排列，思路同上，只是要满足左括号和右括号的对应关系
Leetcode 78. subsets
求一个集合的子集
思路一：同排列，不断加入新元素递归，结束之后删去新元素
思路二：每次遍历都在前一次迭代的每一个结果后面加上当前遍历的数，当然，加之前要保留之前迭代的每一个结果（这个思路类似于workBreakII中的一段代码，也是求一个字符串可以分出来的子集）
Leetcode 17. Letter Combinations of a Phone Number
同Permutation，只是Permutation可以看作从一个数组A向同一个数组A的递归遍历，而本题是从数组digits向数组chs进行遍历
Leetcode 131. Palindrome Partitioning
思路一：可以抽象为插入分隔符的问题，可以看作从左往右，不断往s插入一个分隔符，使得s分为左右两个部分，当left为回文时，接着对right进行递归回溯，插入分隔符（递归回溯可以看作是从左往右分割的过程，左边是最小符合要求的集合，不需要递归，然后对右边继续递归)
思路二：回文串可以用动态规划进行判断
Leetcode 140. Word Break II
思路一：也可以看作插入分隔符的问题，但是正常回溯会导致TLE
思路二：引入dp， 记录字符串s对应的所有句子
leetcode 79. Word Search
正常往四个方向遍历回溯
Leetcode 212. Word Search II
同上，使用键树优化
summary
- 回溯的时间复杂度的判断：
The way I like to think about the runtime of backtracking algorithms is O(b^d), where b is the branching factor and d is the maximum depth of recursion.
Backtracking is characterized by a number of decisions b that can be made at each level of recursion.If you visualize the recursion tree, this is the number of children each internal node has.You can also think of b as standing for “base”, which can help you remember that b is the base of the exponential.
If we can make b decisions at each level of recursion, and we expand the recursion tree to d levels(ie: each path has a length of d), then we get b^d nodes.Since backtracking is exhaustive and must visit each one of these nodes, the runtime is O(b^d). - 许多回溯都是基于Permutation的模板，在递归的for循环中，加入新元素，待递归结束后，删去该元素。在新的循环中在同一个位置加入新元素
- 回溯的参数模板：
a. 加入一个start索引，指示新的递归中应该从哪个元素开始
b. 不使用start索引，每次递归直接传入新的数组/字符串，for循环每次都是从0开始进行遍历（更建议该模板，更有利于思考） - 回溯经常超时，因此会结合dp优化，可以画出解答树，找出计算重复的部分，从而对该部分进行优化
- 还有一类回溯模板是对字符串的分割，可以看作从左往右向字符串插入隔板，将字符串分为左边和右边两个部分，然后令左边是其最小集合，无法递归，然后递归回溯右边的部分
- 求一个数组的子集（无论什么形式上的子集），都可以这样思考：使用迭代而不是递归，每次遍历都在前一次迭代的每一个结果后面加上当前遍历的数，当然，加之前要保留之前迭代的每一个结果