第七章

解决问题在数字1~9之间找出k个数且它们的和为n从而确定组合如n3,

k2,则组合为[[1,2]]

组合问题是取出一组比如封神选六个帅哥当质子团排列问题是按顺序排成一列比如质子团按武力值排名每个月都要打一次架决定最强的算法描述利用回溯算法去确定组合使得算法复杂度为O(n)(n-k1)!百度组合、排列的计算公式即可知这里的n是指问题规模哈千万别望文生义算法难点其实和77没啥大差别就是增加了回溯函数的参数组合的回溯算法模板也熟悉的差不多了看来写博客虽累但效果还是有的。

代码

未剪枝版

tempsum0代表单层递归-回溯过程得到的和self.backtracking(k,n,path,res,1,0)return

resdef

backtracking(self,k,targetsum,path,res,start,tempsum):#

终止条件与77题相比增加了内层判断只有当tempsumtempsum即目标和才加入到res并返回if

(len(path))k:if

targetsumtempsum:res.append(path[:])return#

单层处理#

range(start,10):tempsumipath.append(i)self.backtracking(k,targetsum,path,res,i1,tempsum)tempsum-ipath.pop()图示过程即还原为树形结构与77类似

剪枝代码示例

List[List[int]]:path[]res[]self.backtracking(k,n,path,res,1,0)return

resdef

backtracking(self,k,targetsum,path,res,start,tempsum):#

终止条件if

targetsumtempsum:res.append(path[:])return#

单层处理#

剪枝:9-(k-len(path))29-(k-len(path))11,后面的1是因为ragne函数左取右舍的特性for

range(start,9-(k-len(path))2):tempsumipath.append(i)self.backtracking(k,targetsum,path,res,i1,tempsum)tempsum-ipath.pop()Leetcode

解决问题给定一个仅包含数字

的字符串返回所有它能表示的字母组合这里给出的数字-字母映射表与键盘拇指输入法一致比如输入digits

“23”

输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

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

class

{0:,1:,2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz}#

存储单层递归-回溯结果s#

进行回溯index10代表从digits[0]开始遍历self.backtracking(digits,0,s,res,letter_map)return

resdef

backtracking(self,digits,index1,s,res,letter_map):#

len(digits)0:return#

index1len(digits):res.append(s[:])return#

从letter_map映射表中找到对应的字母集合digit_index

PS:这里s是字符串赋值方式要改变哈ssletters[i]self.backtracking(digits,index11,s,res,letter_map)ss[:-1]今日打卡总结

fighting!