回溯理论基础：
回溯效率:
回溯本质上是穷举，从所有答案中选出想要的。会增加一些剪枝的操作
回溯法解决的问题：
- 组合：N个数中找k个数的集合
- 切割：一个字符串按一定规则有几种切割方式
- 子集：一个N个数的集合中有多少符合条件的子集
- 排列：N个数按照一定规则全排列，有几种排列方式
- 棋盘：N皇后，解数独等
如何理解回溯：
回溯解决的问题可以抽象为树形结构，因为回溯解决的是在集合中递归查找子集，集合大小为树的宽度，递归深度为树的深度
回溯模板：
① 参数及返回值：一般返回值为void，参数是先写逻辑，需要什么参数对应填
void backtracking(参数)
② 终止条件：一般是搜索到叶子节点
if (终止条件){结果return;
}
③ 遍历过程：回溯所形成的树为m叉树，因此是先选择一个孩子节点，再进行递归调用。树中孩子节点的数量是集合的大小
for(选择本层集合中的元素){处理节点;backtracking(路径，选择列表); //递归回溯，撤销处理结果
}
LeetCode 77.组合：
文章链接
题目链接：77.组合
思路
如下图所示，从左向右遍历，当前节点cur可选的集合为(cur, n]
① 参数及返回值：传入cur表示当前访问过的数，count为path中已经记录过的数，path保存路径
② 边界条件：找到叶子节点，即count = 0
③ 遍历过程：for循环遍历(cur, n]，但是可以加剪枝，下图中红色部分其实不需要遍历一次
还需要的节点数量count
访问的最大值为n
因此至多访问到 n - count + 1
访问的区间为(cur, n - count + 1]，又range为左闭右开
因此访问区间为[cur + 1, n - count + 2]
class Solution:def combine(self, n: int, k: int) -> List[List[int]]:self.n = nself.result = []self.backtracking(0, k, [])return self.resultdef backtracking(self, cur, count, path):if count == 0:self.result.append(path[:])returnfor i in range(cur + 1, self.n - count + 2):path.append(i)self.backtracking(i, count - 1, path)path.pop()LeetCode 216.组合Ⅲ：
文章链接
题目链接：216.组合Ⅲ
思路
和上一题思路相同，都是从左向右进行遍历
① 传入参数：cur表示当前访问的节点，subsum表示目标和(每次递归都会减去当前节点的值)，path记录路径，count记录path还差多少个数
② 边界条件：访问到叶子节点
if count == 0 and subsum == 0: # 目标叶子节点self.result.append(path[:])return
elif count == 0 or subsum == 0: # 非目标叶子节点和剪枝（subsum为0，但是没到叶子）return
③ 递归遍历：for循环的值的范围为[cur + 1, 9]，可以进行剪枝
1）可取到的最大值为min(9, subsum) = maxdigital
2）path需要取到的剩余元素个数为count，那么for循环至多到maxdigital - count + 1（maxdigital - x + 1 = count → x = maxdigital - count + 1）
又range为左闭右开区间，因此范围为[cur + 1, maxdigital - count + 2)
class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.result = []self.backtracking(0, n, [], k)return self.resultdef backtracking(self, cur, subsum, path, count):if count == 0 and subsum == 0:self.result.append(path[:])returnelif count == 0 or subsum == 0:returnmaxdigital = min(9, subsum)for i in range(cur + 1, maxdigital - count + 2):path.append(i)self.backtracking(i, subsum - i, path, count - 1)path.pop()LeetCode 17.电话号码的字母组合：
文章链接
题目链接：17.电话号码的字母组合
思路：
- 回溯
本题与上面几题不同，上面几题是在同一个集合中求组合，本题是在不同集合中求组合，如下图，每一层确定一个数字对应的字母，树的深度为数字的个数
可以使用二维数组保存数字与字母对应关系，也可以用字典/映射保存。但是都需要考虑到输入0,1，*，#按键等异常情况，面试都会问（首先要知道有这些异常，其次面试时需要考虑到）
① 传入参数：digits传入的字符串，index当前访问的数字，path / s记录当前保存的组合
② 边界条件：index如果是从0开始的，那么边界条件为index == len(digits)；若index从len(digits) - 1开始，那么边界条件为index = 0 (此时添加s / path时需要进行反转)
③ 遍历过程：根据数字得到对应的字母集合，遍历该字母集合
"""
考虑了异常情况，使用字符串记录路径
"""
class Solution:def letterCombinations(self, digits: str) -> List[str]:if len(digits) == 0:return []self.digitsDict = {"0":"","1":"","2":"abc", "3":"def","4":"ghi","5":"jkl","6":"mno", "7":"pqrs","8":"tuv","9":"wxyz"}self.result = []self.backtracking(digits, len(digits) - 1, "")return self.resultdef backtracking(self, digits, index, s): # index是从后往前遍历if index == -1:self.result.append(s[::-1]) # 记得反转returnletters = "" # 不是正常情况就是异常if 2 <= int(digits[index]) <= 9: # 正常情况letters = self.digitsDict[digits[index]]for letter in letters:s = s + letterself.backtracking(digits, index - 1, s)s = s[:-1]"""
使用list保存路径
"""
class Solution:def letterCombinations(self, digits: str) -> List[str]:if len(digits) == 0:return []self.digitsDict = {"2":"abc", "3":"def","4":"ghi","5":"jkl","6":"mno", "7":"pqrs","8":"tuv","9":"wxyz"}self.result = []self.backtracking(digits, len(digits) - 1, [])return self.resultdef backtracking(self, digits, index, path): # index是从后往前遍历if index == -1:self.result.append("".join(path[::-1])) # 记得反转returnletters = self.digitsDict[digits[index]]for s in letters:path.append(s)self.backtracking(digits, index - 1, path)path.pop()
- 不使用回溯
直接遍历digits，使用result记录到目前已经得到的字符串，每次遍历将result中的全部元素与num对应的字母进行拼接（记得考虑异常情况）
class Solution:def letterCombinations(self, digits: str) -> List[str]:if len(digits) == 0:return []digitDict = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}result = [""]for num in digits:result = [s + letter for letter in digitDict[num] for s in result]return result
