代码随想录算法训练营第七天|组合、组合总和III和电话号码的字母组合

组合

【题目简介】

【回溯解法】

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:# 回溯算法startIndex = 1self.path = []self.result = []self.traversal(n, k, startIndex)return self.resultdef traversal(self, n, k, startIndex):if len(self.path) == k:self.result.append(self.path[:])  # 这里需要加上[:]!return               # 至此之后，没有必要再向后遍历了！# 这里是从深度上进行剪枝！need_num = k - len(self.path)for i in range(startIndex, n + 1):  # 从广度上进行剪枝rest_num = n - i + 1if (rest_num < need_num): break# 当还需要的项目数大于序列剩余的项目时，则终止self.path.append(i)self.traversal(n, k, i + 1)self.path.pop()

1. 在这里path和result我习惯上使用全局变量
2. 剪枝的方面：深度方向剪枝，以及广度方向的剪枝！

组合总和III

【题目简介】

【回溯解法】

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.path = []self.result = []self.backtracking(n, k, 1)return self.resultdef backtracking(self, n, k, startIndex):if sum(self.path) == n and len(self.path) == k:self.result.append(self.path[:])return                     # 终止条件 兼 深度剪枝if sum(self.path) > n: return  # 深度剪枝#? startIndex的作用是啥？ 避免重复的组合！控制当前递归层次的递归元素范围for i in range(startIndex, 10): need_num = k - len(self.path)rest_num = 10 - i + 1if rest_num < need_num: break  # 广度剪枝self.path.append(i)self.backtracking(n, k, i + 1)self.path.pop()

1. 这类题最为关键的就是明白startIndex的作用（元素不允许重复出现！且组合不会重复出现 🌟好好悟 🌟）！以及各类剪枝的位置；
2. 明确深度剪枝要执行的位置！明确广度剪枝要执行的位置！

电话号码的字母组合

【题目简介】

【回溯解法】

class Solution:def letterCombinations(self, digits: str) -> List[str]:# 回溯解法# 如果已知2和3的字符组合，进行双for循环的自由组合即可# 如何根据数字字符获取到对应的字母字符串？或者存储结构？self.intchar_strchars = ["","","abc",'def',"ghi","jkl","mno","pqrs","tuv","wxyz"]if len(digits) == 0: return []self.digits = list(digits)# 被遍历的元素来自于多个集合！！！起始不同迭代层次的元素范围不同self.path = []self.result = []self.backtracking(len(self.digits), 0)return self.resultdef backtracking(self, k, deep):if len(self.path) == k:self.result.append("".join(self.path[:]))returndigit = self.digits[deep]for i in self.intchar_strchars[int(digit)]:self.path.append(i)self.backtracking(k, startIndex + 1)self.path.pop()
```1. 除了本题中的跟题目应用相关的相关结构体的构建，比如数字和对应字符串对应关系的存储结构；其他的就是每一个数字对应的字符串集合就是每层迭代深度下的for循环遍历集合！