代码随想录算法训练营第25天| 第七章 回溯算法part02: leetcode 216、leetcode 17

Part I : 回溯算法基础

对回溯算法不清楚的可以参看前一篇：代码随想录算法训练营第24天| 第七章 回溯算法part01 理论基础、leetcode 77

Part II: 相关题目

Leetcode 216.组合总和III

• 解决问题：在数字1~9之间，找出k个数且它们的和为n从而确定组合，如n=3, k=2,则组合为[[1,2]] （组合问题是取出一组，比如封神选六个帅哥当质子团；排列问题是按顺序排成一列，比如质子团按武力值排名，每个月都要打一次架决定最强的）
• 算法描述：利用回溯算法去确定组合，使得算法复杂度为O(n)=(n-k+1)!（百度组合、排列的计算公式即可知，这里的n是指问题规模哈，千万别望文生义），
• 算法难点：其实和77没啥大差别，就是增加了回溯函数的参数，组合的回溯算法模板也熟悉的差不多了，看来写博客虽累，但效果还是有的。
• 代码：

# 未剪枝版
class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:path=[] # 用于接收单层递归-回溯结果res=[] # 用于接收总递归-回溯结果# 这里的start=1，代表从数字1开始；# tempsum=0，代表单层递归-回溯过程得到的和self.backtracking(k,n,path,res,1,0)return resdef backtracking(self,k,targetsum,path,res,start,tempsum):# 终止条件：与77题相比，增加了内层判断，只有当tempsum=tempsum即目标和才加入到res，并返回if (len(path))==k:if targetsum==tempsum:res.append(path[:])return# 单层处理# 横向遍历：只使用数字1到9for i in range(start,10):tempsum+=ipath.append(i)self.backtracking(k,targetsum,path,res,i+1,tempsum)tempsum-=ipath.pop()

• 图示过程（即还原为树形结构，与77类似）
  

• 剪枝代码示例

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:path=[]res=[]self.backtracking(k,n,path,res,1,0)return resdef backtracking(self,k,targetsum,path,res,start,tempsum):# 剪枝时必须增加该终止条件（若不加则报错，具体原因看上面的图示）if tempsum>targetsum:return# 终止条件if (len(path))==k:if targetsum==tempsum:res.append(path[:])return# 单层处理# 横向遍历：只使用数字1到9# 剪枝:9-(k-len(path))+2=9-(k-len(path))+1+1,后面的1是因为ragne函数左取右舍的特性for i in range(start,9-(k-len(path))+2):tempsum+=ipath.append(i)self.backtracking(k,targetsum,path,res,i+1,tempsum)tempsum-=ipath.pop()

---

Leetcode 17.电话号码的字母组合

• 解决问题：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合，这里给出的数字-字母映射表与键盘拇指输入法一致，比如输入：digits = “23”
  输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

• 算法描述：利用回溯算法去确定组合，使得算法复杂度为O(n)=(n-k+1)!（百度组合、排列的计算公式即可知，这里的n是指问题规模哈，千万别望文生义）

• 算法难点：对我来说是加上了数字-字母映射表后的变化啦。

• 代码：

class Solution:def letterCombinations(self, digits: str) -> List[str]:# 数字-字母映射表letter_map = {0:'',1:'',2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'}# 存储单层递归-回溯结果s=''# 存储总递归-回溯结果res=[]# 进行回溯，index1=0，代表从digits[0]开始遍历self.backtracking(digits,0,s,res,letter_map)return resdef backtracking(self,digits,index1,s,res,letter_map):# 根据测试用例要加上这个终止条件，否则返回[""]而非[]if len(digits)==0:return# 设置终止条件，如果遍历完了digits则返回if index1==len(digits):res.append(s[:])return# 从letter_map映射表中找到对应的字母集合digit_index = int(digits[index1])letters = letter_map[digit_index]# 处理遍历-递归-回溯过程for i in range(len(letters)):# PS:这里s是字符串，赋值方式要改变哈s=s+letters[i]self.backtracking(digits,index1+1,s,res,letter_map)s=s[:-1]

今日打卡总结

有了昨天的基础，今天的博客轻松些了~
之前差的day2~day23的博客也要慢慢补上来，
fighting!