代码随想录算法训练营第22、23天|回溯理论基础、组合问题、216.组合总和III 17.电话号码的字母组合

本文主要是介绍代码随想录算法训练营第22、23天|回溯理论基础、组合问题、216.组合总和III 17.电话号码的字母组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

前言

回溯理论基础

回溯可以用于解决一些经典的问题，可以看到理论框架，



回溯的框架

77、组合问题

思路

回溯算法引入：C5-2这样的组合问题可以用两层for循环来实现，C5-3就是再套一层for循环，如果是C100-50呢？50层for循环。所以需要使用回溯算法；

• 核心在于：递归几次就是for循环几次
• 回溯算法就是使得这样的递归可以得到想要的结果：💖💜即，for给每一个元素遍历的时候，每一个元素都是需要递归的，所以进入了第一个元素之后出来需要回溯，pop掉第一个元素，然后再进入第二个元素； 所以回溯是紧跟在递归的后面，也是只在单层逻辑里面

按照老师的解题思路
首先看一下构建的树形结构

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中可以发现n相当于树的宽度，k相当于树的深度。

那么如何在这个树上遍历，然后收集到我们要的结果集呢？

图中每次搜索到了叶子节点，我们就找到了一个结果。

相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
？？？有毒吧突然卡了写不了
回溯三部曲【看教程】
传入传出：定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。传入startIndex来记录下一层递归，搜索的起始位置。

终止条件：path记录的长度等于k了

其中单层逻辑：
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。

方法一 没有剪枝

下面是我自己写的代码
💦💘同样的错误：结果传入的时候必须是浅复制之后的self.result.append(self.path[:])，而不是self.result.append(self.path)，因为python是指向变量空间，self.path最后为空，这会导致结果为空

class Solution(object):def __init__(self):self.path = []self.result = []def backtrack(self,n,k,startindex):#终止条件if len(self.path) == k:self.result.append(self.path[:])#必须要是复制切片return#单层递归逻辑，也就是处理一个节点for i  in range(startindex,n+1):print(i)self.path.append(i)print(self.path)self.backtrack(n,k,i+1)self.path.pop()return def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""self.backtrack(n,k,1)return self.result

方法二 剪枝

老师讲解了一个非常常见的剪枝思路：单层逻辑中修改for遍历的范围
具体思路：如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
具体实现：

注意：range是不包括右边界的，所以需要再+1

class Solution(object):def __init__(self):self.path = []self.result = []def backtrack(self,n,k,startindex):#终止条件if len(self.path) == k:self.result.append(self.path[:])#必须要是复制切片return#单层递归逻辑，也就是处理一个节点for i  in range(startindex,n-(k-len(self.path))+2):print(i)self.path.append(i)print(self.path)self.backtrack(n,k,i+1)self.path.pop()return def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""self.backtrack(n,k,1)return self.result

216.组合总和III

思路

方法一 没有剪枝

这是没听讲解直接写的，确实有了前面的基础就很简答了。

class Solution(object):def __init__(self):self.result = []self.path = []self.count = 0def backtrace(self,target,k,startindex):if len(self.path) == k:if self.count == target:self.result.append(self.path[:])returnfor i in range(startindex,10):self.path.append(i)self.count += iself.backtrace(target,k,i+1)self.count -= iself.path.pop()def combinationSum3(self, k, n):""":type k: int:type n: int:rtype: List[List[int]]"""self.backtrace(n,k,1)return self.result

方法二 有剪枝

当然，剪枝的思路有两个

1. size角度：和之前一样，就是改变for循环语句
   for i in range(startindex,10-(k-len(self.path))+1):
2. count的角度，如果当前的sum已经大于目标sum了，就返回。

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:if currentSum == targetSum:result.append(path[:])returnfor i in range(startIndex, 9 - (k - len(path)) + 2):  # 剪枝currentSum += i  # 处理path.append(i)  # 处理self.backtracking(targetSum, k, currentSum, i + 1, path, result)  # 注意i+1调整startIndexcurrentSum -= i  # 回溯path.pop()  # 回溯

17.电话号码的字母组合

思路

本题思路依然和之前的差不多；不多要注意细节的传入参数，我自己就没有想出来
回溯三部曲

1. 传入传出参数：传入的应该是digits和指向digits的index（表示是digits中第几个数）；
2. 终止条件：如果index大于digit-size，说明到头了
3. 单层递归逻辑：首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。

💛本题注意点和小细节

• 💘使用map来表征数字和对应的字母；但是进一步可以用list来创建哈希表，其下标就是数字，元素值就是数字对应的字母（所以0和1是空的）
• digits[index]得到的结果是“2”这样的，要记得转换为数字类型；在c++中处理的方法是int digit = digits[index] - ‘0’
• 对于string类型的处理：python是string类型直接+就行，string类型删除的话使用[:-1]的方式；下面方法一3使用的是列表最后转为字符串，result.append(‘’.join(path))
• 

方法一

下面是我自己写 的

class Solution(object):def __init__(self):self.map_ = [" ",#0" ",#1"abc",#2"def",#3"ghi",#4"jkl",#5"mno",#6"pqrs",#7"tuv",#8"wxyz",#9]self.result = []self.s = ""def backtrace(self,digits,index_):if index_ == len(digits):self.result.append(self.s)returnfor i in self.map_[int(digits[index_])]:self.s += iself.backtrace(digits,index_+1)self.s = self.s[:-1]def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""if len(digits) == 0:return self.resultself.backtrace(digits,0)return self.result

方法一2 隐藏回溯

具体方法：self.s不再设为全局变量，而是变成参数每次传进去；
回溯的是时候变成self.backtrace(digits,index_+1,s+letter)；这样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 = []def getCombinations(self, digits, index, s):if index == len(digits):self.result.append(s)returndigit = int(digits[index])letters = self.letterMap[digit]for letter in letters:self.getCombinations(digits, index + 1, s + letter)def letterCombinations(self, digits):if len(digits) == 0:return self.resultself.getCombinations(digits, 0, "")return self.result

方法一3 不用字符串而是列表来处理

    def getCombinations(self, digits, index, path, result):if index == len(digits):result.append(''.join(path))returndigit = int(digits[index])letters = self.letterMap[digit]for letter in letters:path.append(letter)self.getCombinations(digits, index + 1, path, result)path.pop()def letterCombinations(self, digits):result = []if len(digits) == 0:return resultself.getCombinations(digits, 0, [], result)return result

总结

这篇关于代码随想录算法训练营第22、23天|回溯理论基础、组合问题、216.组合总和III 17.电话号码的字母组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---