代码随想录 - Day31 - 回溯：组合问题

代码随想录 - Day31 - 回溯：组合问题

77. 组合

最容易想到的：k层for循环。
显然不能写那么多层for循环，所以该方法pass
使用回溯法：
用递归解决嵌套层数的问题
n相当于树的宽度，k相当于树的深度。
找到最深处的叶子节点即为找到一个结果，把结果收集起来就是最终答案。

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:result = []                         # 存放结果集self.backtracking(n, k, 1, [], result)return resultdef backtracking(self, n, k, startIndex, path, result):if len(path) == k:result.append(path[:])returnfor i in range(startIndex, n + 1):  # 需要优化的地方path.append(i)                  # 处理节点self.backtracking(n, k, i + 1, path, result)path.pop()                      # 回溯，撤销处理的节点

剪枝优化：
可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数已经不足需要的元素个数了，那就没必要搜索了。
优化过程：

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:result = []                         # 存放结果集self.backtracking(n, k, 1, [], result)return resultdef backtracking(self, n, k, startIndex, path, result):if len(path) == k:result.append(path[:])returnfor i in range(startIndex, n - (k - len(path)) + 2):  # 剪枝优化path.append(i)                  # 处理节点self.backtracking(n, k, i + 1, path, result)path.pop()                      # 回溯，撤销处理的节点

216. 组合总和 III

找到和为n的k个数的组合，且k在1~9之间

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:result = []                         # 存放结果集self.backtracking(n, k, 0, 1, [], result)return resultdef backtracking(self, targetSum, k, currentSum, startIndex, path, result):if currentSum > targetSum:          # 剪枝操作return                          # 如果path的长度等于k但currentSum不等于targetSum，则直接返回if len(path) == k and currentSum == targetSum:result.append(path[:])returnfor i in range(startIndex, 10):     # 剪枝优化currentSum += ipath.append(i)                  # 处理节点self.backtracking(targetSum, k, currentSum, i + 1, path, result)currentSum -= ipath.pop()                      # 回溯，撤销处理的节点

剪枝优化：
已选元素总和如果已经大于n了，那么往后遍历就没有意义了，直接剪掉。

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:result = []                         # 存放结果集self.backtracking(n, k, 0, 1, [], result)return resultdef backtracking(self, targetSum, k, currentSum, startIndex, path, result):if currentSum > targetSum:          # 剪枝操作return                          # 如果path的长度等于k但currentSum不等于targetSum，则直接返回if len(path) == k and currentSum == targetSum:result.append(path[:])returnfor i in range(startIndex, 9 - (k - len(path)) + 2):  # 剪枝优化currentSum += ipath.append(i)                  # 处理节点self.backtracking(targetSum, k, currentSum, i + 1, path, result)currentSum -= ipath.pop()                      # 回溯，撤销处理的节点

在一开始判断的时候不能把if currentSum > targetSum写在if len(path) == k里面。如果写在里面，就忽略掉了currentSum > targetSum && len(path) != k的情况。

17. 电话号码的字母组合

使用map或定义一个二维数组，实现数字和字母的映射

def __init__(self):self.letterMap = ["",     # 0"",     # 1"abc",  # 2"def",  # 3"ghi",  # 4"jkl",  # 5"mno",  # 6"pqrs", # 7"tuv",  # 8"wxyz"  # 9]self.result = []    # 记录结果self.s = ""         # 字符串s来收集叶子节点的结果

完整代码：

class Solution:def __init__(self):self.letterMap = ["",     # 0"",     # 1"abc",  # 2"def",  # 3"ghi",  # 4"jkl",  # 5"mno",  # 6"pqrs", # 7"tuv",  # 8"wxyz"  # 9]self.result = []self.s = []def backtracking(self, digits, index):if index == len(digits):self.result.append("".join(self.s))returndigit = int(digits[index])letters = self.letterMap[digit]for i in range(len(letters)):self.s.append(letters[i])self.backtracking(digits, index + 1)self.s.pop()def letterCombinations(self, digits: str) -> List[str]:if len(digits) == 0:return self.resultself.backtracking(digits, 0)return self.result

由于题目中限定了2~9，所以并未考虑0和1没有对应字母的情况。在实际问题中应当考虑到。

小总结

做了这几道题后，发现它们的解题代码都有共通之处，于是自己总结了一下。

def __init__(): # 需要的时候才写# 定义全局变量def backtracking(self, 参数1, 参数2, ...):# 回溯算法if 相等:result.append()returnfor ...:# 回溯代码self.backtracking() # 递归# 回溯代码def function():# 排除某些情况self.backtracking() # 递归return result