代码随想录D22-23 回溯算法01-02 Python

理论回顾

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

理解回溯

回溯法解决的问题都可以抽象为树形结构，是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯法模板

• 回溯函数模板返回值以及参数
• 回溯函数终止条件
• 回溯搜索的遍历过程

77. 组合

要点：

以暴搜为起点进行思考的话，搜索k为2时的结果可以使用两个嵌套for循环实现。将k拓展到大于2的数，可以发现用同样的思路解决问题就需要做k次嵌套的for循环。肯定无法解决本题的问题。

实际上，在回溯算法中，k次嵌套其实就是算法中递归的深度了，通过递归来解决不定次数的嵌套循环即可轻松解决。

解法：

树形结构：

输入输出：两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。 两个参数，既然是集合n里面取k个数，那么n和k是两个int型的参数。然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历

终止条件：到达满足输出要求（叶子节点）

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

实现：

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:# 创建所有结果的总表results = list()self.backtracking(n, k, 1, [], results)return resultsdef backtracking(self, n, k, start_idx, path, results):# 终止条件 当path长度达到了要求 表示已经深入到了叶子节点if len(path) == k:results.append(path[:])returnfor i in range(start_idx, n + 1):path.append(i)# 使用递归来完成等价多个for循环的嵌套self.backtracking(n, k, i + 1, path, results)# 回溯步 撤销本层的遍历结果path.pop()

将for循环的右区间换成下面这个表达，就可以进行特定情况下的剪枝。含义是，已经选择的元素个数 len(path) ; 还需要的元素个数为: k - len(path)，还需要选择的元素数量不能大于数组中剩余的数量。

for i in range(startIndex, n - (k - len(path)) + 2):pass

216. 组合总和 III

要点：

转换成树形问题之后，可以观察到和组合的相似之处。遍历的宽度是确定值9个数，而深度则是k，目标值是n。 

解法：

全局变量：依然需要一维数组path来存放符合条件的结果，二维数组result来存放结果集

输入输出：1. 目标和n；2. 数量k；3. 目标和sum；4. 起始索引start_idx

终止条件：path.size() 和 k相等了，就终止;

单步逻辑：添加一步总和累加和回溯减去即可

实现：

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:results = list()self.backtracking(n, k, 0, 1, [], results)return resultsdef backtracking(self, tar_sum, num_count, cur_sum, start_idx, path, results):if cur_sum > tar_sum:returnif len(path) == num_count:if cur_sum == tar_sum:results.append(path[:])returnfor i in range(start_idx, 9 - (num_count - len(path)) + 2):path.append(i)cur_sum += iself.backtracking(tar_sum, num_count, cur_sum, i + 1, path, results)cur_sum -= ipath.pop()

17. 电话号码的字母组合

要点：

一个数字会对应多个字母，可能出现多个数字。因此，这里需要一个index来指向正在遍历的数字。

实现：

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 get_comb(self, digits, idx, sub_res):# 当索引和数字总长一致时，添加字母结果并返回if idx == len(digits):self.result.append(sub_res)return# 通过数字取字母数组letter_str = self.letterMap[int(digits[idx])]# 通过for循环将每个数组中的结果依次加入子结果for letter in letter_str:self.get_comb(digits, idx + 1, sub_res + letter)def letterCombinations(self, digits: str) -> List[str]:if len(digits) == 0:return []self.get_comb(digits, 0, '')return self.result

39. 组合总和

要点：

本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。终止条件则应设定为超过目标值则判断并返回。

解法：

全局变量：一个sub_res存放单个path，一个results存放所有结果

输入输出：和组合总和基本类似，原始数组，目标值，记录一个当前值总和，开始索引，分支结果和全部结果。

和之前的不同在于，在backtrack中，将start_idx设置成当前循环索引，即不用额外做i+1。

实现：

class Solution:def backtrack(self, candidates, target, cur_sum, start_idx, sub_res, results):if cur_sum > target:returnif cur_sum == target:results.append(sub_res[:])return for i in range(start_idx, len(candidates)):cur_sum += candidates[i]sub_res.append(candidates[i])# 之前使用了i + 1 这里直接从i开始表示可以重复使用self.backtrack(candidates, target, cur_sum, i, sub_res, results)cur_sum -= candidates[i]sub_res.pop()def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:results = []self.backtrack(candidates, target, 0, 0, [], results)return results

40. 组合总和 II

要点：

这里指定了每个数字只能使用一次，数组candidates的元素是有重复的，且解集中不能有重复结果。

在回溯中的去重，本质就是使用过的元素不能重复选取。 已知组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 会导致不能彻底理解去重。

转换成树形结构可以总结，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

想要进行树层的去重，首先需要对候选数组进行一次排序。除此之外，此题还需要加一个bool型数组used，来记录每个元素的使用情况。最核心的理解在于回溯中的递归，以上图为例，假设在第一个分支里已经取过了第二个1，那么在第二个分支中应该忽略掉连续取两个1的情况，因为同样的结果已经出现在了第一个递归的分支中。

• used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
• used[i - 1] == false，说明同一树层candidates[i - 1]使用过

这里就体现了排序的必要性，只有先进行排序才能确保：只对前一位的使用情况进行判断就能够去除所有重复；大小颠倒的组合情况被自然消除了。

解法：

输入参数：输入数组，目标数值，总和，起始索引，已使用元素记录，单条路径，最终结果

终止条件：达到target返回，遇到重复或超过目标值分别跳过和停止递归

单步逻辑：按照上述描述进行去重，传入新的startindex，进行递归计算

实现：

class Solution:def backtrack(self, candidates, target, total, start_idx, used, path, result):if total == target:result.append(path[:])returnfor i in range(start_idx, len(candidates)):# 去重逻辑 只去除相同数字 且上一个相同数字没用的情况if i > start_idx and candidates[i] == candidates[i - 1] and not used[i - 1]:continue# if total > target:break# 三个变量依次修改total += candidates[i]path.append(candidates[i])used[i] = True# 从i + 1开始 保证正确递归顺序self.backtrack(candidates, target, total, i + 1, used, path, result)used[i] = Falsepath.pop()total -= candidates[i]def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:used = [False] * len(candidates)result = []candidates.sort()self.backtrack(candidates, target, 0, 0, used, [], result)return result

131. 分割回文串

要点：

这里提出了需要返回所有可能的分割方案，观察可得所谓的分割，其实也是一种组合问题。

例如对于字符串abcdef：

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个。
• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段。

 所以此类切割的问题可以转换成树形问题

解法:

输入输出：本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。

单步逻辑：递归循环中如何截取子串？在一个子循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。和组合问题一致。在单步过程中判断每次切割出的子串是不是回文字串。如果是，那么进行下一步递归。

终止条件：当i已经是最后一位，则停止

实现：

class Solution:def backtrack(self, s, start_idx, path, results):if start_idx == len(s):results.append(path[:])returnfor i in range(start_idx, len(s)):## 右侧需要从start的下一位开始 遵循python切片左闭右开if s[start_idx: i+1] == s[start_idx: i+1][::-1]:path.append(s[start_idx: i+1])self.backtrack(s, i + 1, path, results)path.pop()def partition(self, s: str) -> List[List[str]]:results = list()self.backtrack(s, 0, [], results)return results