算法通关村第十八关：青铜挑战-回溯是怎么回事

青铜挑战-回溯是怎么回事

回溯，最重要的算法之一
主要解决一些暴力枚举也搞不定的问题，例如组合、分割、子集、排列、棋盘等

从性能角度来看回溯算法的效率并不高，但对于这些暴力都搞不定的算法能出结果就很好了，效率低点没关系

回溯可视为递归的拓展，很多思想和解法都与递归密切相关，对比递归来分析其特征会理解的更深刻

举例说明递归和回溯的区别：
设想一个场景，某猛男想脱单，两种策略：

1. 递归策略：先与意中人制造偶遇，然后了解人家的情况，然后约人家吃饭，有好感之后尝试拉人家的手，没有拒绝就表白
2. 回溯策略：先统计周围所有单身女孩，然后一个一个表白，被拒绝就说”我喝醉了“，然后就当啥也没有发生，继续下一个

回溯最大的好处：有非常明确的模板
所有的回溯都是一个大框架，因此透彻理解回溯的框架是解决一切回溯问题的基础

回溯不是万能的，解决的问题也是非常明确的，例如组合、分割、子集、排列、棋盘等
不过这些问题具体处理时又有很多不同

回溯可视为递归的拓展，代码结构特别像深度遍历N叉树
难点：回溯在递归语句之后有个”撤销“的操作。
好比谈了个新女朋友，来你家之前，要将前任的东西赶紧藏起来。回溯也一样，有些信息是前任的，要处理掉才能重新开始。

回溯的模板如下

void backtracking(参数){if(终止条件){存放结果;return;}for(选择本层集合中元素(画成树，就是树节点孩子的大小)){处理节点;backtracking(参数);回溯，撤销处理结果}
}

1. 从N叉树说起

二叉树的前序遍历

class TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Nonedef tree_dfs(root):if root is None:returnprint(root.val)tree_dfs(root.left)tree_dfs(root.right)

N叉树的前序遍历

class TreeNode:def __init__(self, val):self.val = valself.children = []def tree_dfs(root):# 递归终止条件if root is None:return# 节点处理print(root.val)# 通过循环，分别遍历N个子树for i in root.children:tree_dfs(i)

回溯模板与N叉树的遍历模板非常像！！！

2. 为什么有的问题暴力枚举也不行

什么问题暴力枚举也不行？

举个例子：

LeetCode77 组合
https://leetcode.cn/problems/combinations/

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

n=4, k=2时，双层暴力枚举

def violent_enumeration():res = []for i in range(1, 5):for j in range(i + 1, 5):res.append((i, j))return resif __name__ == '__main__':print(violent_enumeration())  # [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

n=10, k=3时，三层暴力枚举

def violent_enumeration():res = []for i in range(1, 11):for j in range(i + 1, 11):for k in range(j + 1, 11):res.append((i, j, k))return res

k未知时，循环次数未知，这时暴力枚举就失效了

这就是组合类型问题，除此之外，子集、排列、切割、棋盘等方面都有类似的问题，我们需要找到更好的方式

3. 回溯=递归+局部枚举+手动撤销（放下前任）

继续研究
LeetCode77 组合
https://leetcode.cn/problems/combinations/

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

n=4, k=2时

n=5, k=3时

从图中我们可以发现，元素个数n相当于树的宽度(横向)，每个结果的元素个数k相当于树的深度(纵向)
此外还有一下规律

• 局部枚举：每次都是从类似 [1,2,3,4] 这样的序列进行枚举，越往后枚举范围越小
• 递归：再看n=5,k=3时图中红色大框部分，执行过程与n=4,k=2处理过程一直，时可以递归的子结构
• 手动撤销：观察图中可以看到，取3得到[1,2,3]之后，需要将3撤掉，再继续取4得到[1,2,4]
  • 对应的代码操作:
  • 将第一个结果放到 path中，path=[1]
  • 将第二个结果放到 path中，path=[1,2]
  • 将第三个结果放到 path中，path=[1,2,3]
  • 将结果输出，撤销3, path=[1,2]
  • 继续枚举，将第三个结果放到 path中，path=[1,2,4]
  • …

综上，可以得到 回溯=递归+枚举+手动撤销

这就是回溯的基本规律，掌握之后就可写出完整的回溯代码了

回溯代码实现

import copyclass Solution:def combine(self, n: int, k: int) -> List[List[int]]:def dfs(k, n, begin, path, res):# 递归终止条件是：path的长度等于kif len(path) == k:res.append(copy.deepcopy(path))return# 枚举：针对一个节点，遍历可能的搜索起点for i in range(begin, n+1):# 像路径变量里添加一个数，就是树枝的值path.append(i)# 搜索起点加1，缩小范围，为下一轮递归做准备，因为不允许出现重复的元素dfs(k, n, i + 1, path, res)# 手动撤销path.pop()res = []if k <= 0 or n < k:return respath = []begin = 1dfs(k, n, begin, path, res)return res

4. 图解为什么有个撤销的操作

暂无，理解了上一小节的 手动撤销 即可

5. 回溯热身-再论二叉树的路径问题

5.1 输出二叉树的所有路径

LeetCode 257
https://leetcode.cn/problems/binary-tree-paths/

思路分析

方法1：深度优先搜索
深度优先搜索就是从根节点开始一直找到叶子结点，这里可以先判断当前节点是不是叶子结点，再决定是不是向下走，如果是叶子结点，我们就增加一条路径。这个之前学习，这里不再赘述

方法2：回溯
从回溯的角度分析，得到第一条路径ABD之后怎么找到第二条路径ABE，这里就是先将D撤销，然后再继续递归就可以了

难点，手动撤销

代码实现

方法1：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:def search_path(node, path):if not node:return path += str(node.val)if not node.left and not node.right:paths.append(path)else:path += "->"search_path(node.left, path)search_path(node.right, path)paths = []if root:search_path(root, path="")return paths

方法2：回溯

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:def search_path(node, path, paths):if node is None:returnpath.append(str(node.val))if node.left is None and node.right is None:paths.append('->'.join(path))for i in [node.left, node.right]:search_path(i, path, paths)path.pop() # 返回上一层递归时，要让当前路径恢复原样paths = []path = []if root:search_path(root, path, paths)return paths

5.2 路径总和问题

LeetCode 113 路径总和 II
https://leetcode.cn/problems/path-sum-ii/

思路分析

目标：路径总和 targetSum=22

• 根节点5
• 需要左侧或右侧target_sum=22-5=17
• 继续看左子树node(4)，需要node(4)左子树或右子树满足 target_sum=17-4=13
• 依次类推 … …

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import copyclass Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:def find(node, target_sum, path, paths):if node is None:returnpath.append(node.val)if node.left is None and node.right is None and node.val == target_sum:paths.append(copy.deepcopy(path))target_sum -= node.valfor i in [node.left, node.right]:find(i, target_sum, path, paths)path.pop()paths = []path = []if root:find(root, targetSum, path, paths)return paths

注：不想用copy，也可以用 path[:] 替代