回溯算法
1 什么是回溯？
回溯是一种算法技术，常用于组合问题中有技巧地穷尽所有可能组合的技术。
它一步一步递归地解决问题，并在任何时间点删除那些不满足问题约束的解决方案。
它是一种精练的暴力方法，可以尝试所有可能的解决方案，并从中选择最好的解决方案。
回溯法通常用于存在多个可行解的情况。
回溯一词意味着——如果当前的解不合适，那么消除它，回溯（返回）并检查其他解决方案。
2 回溯是如何工作的？
在任何回溯问题中，该算法都试图找到一条有中间检查点可行解的路径。如果它们不能导致可行的解决方案，问题可以从检查点回溯到另一条路径来寻找解。
考虑以下示例：
S是问题的出发点。
我们从S开始，通过中间点I1找到解S1。
但是，我们发现解S1不是我们问题的可行解。
因此，我们从S1回溯（返回），回到I1，回到S，然后检查可行解S2。
这个过程一直持续到我们找到一个可行的解。
在这里，S1和S2不是可行解。
根据我们的例子，只有S3是一个可行解。
当我们看这个例子时，可以看到我们遍历所有可能的组合，直到得到可行的解。
这就是为什么我们说回溯是一种暴力算法技术。
上述问题的树表示称为“空间状态树”。它表示给定问题的所有可能状态（解或非解）。
3 回溯算法步骤
回溯算法可以概括为：
Step1 如果当前点是可行的解决方案，则返回success
Step2 否则，如果所有路径都已用尽（即当前点是终点），则返回失败，因为我们没有可行解
Step3 否则，如果当前点不是终点，则返回并探索其他点，然后重复上述步骤。
4 回溯案例
假设如下树有的叶子是坏的，现在想找到一个是good标签的路径。您可以通过撤销最近的选择并尝试该选项集中的下一个选项来回溯以继续搜索好的叶子。如果没有选项，请撤消将您带到此处的选项，然后在该节点上尝试另一个选项。如果你最后在根上没有选择，就没有好的叶子可以找到。
- 从根开始，你的选择是A和B。你选择A。
- 在A，你的选择是C和D。你选择C。
- C是坏的。回到A。
- 在A，您已经尝试了C，但失败了。试试D。
- D不好。回到A。
- 现在，你别无选择。回到根上。
- 在Root上，你已经试过A。试试B。
- 在B，你的选择是E和F。试试E。
- E是好的。
5 回溯算法关键点
回溯算法关键点，从定义便能窥见一斑，关键点主要包括：
- 要结合递归遍历所有路径
- 每次回溯要能准确返回到检查点或状态点
- 尽可能今早判断出不满足的路径，也成为剪枝
6 回溯算法注意事项
回溯是为了解决组合问题，是精进的穷举算法。需要注意：
- 遍历所有可能情况，不能出现遗漏
- 回溯不能再重复之前遍历的情况，否则会陷入死循环
- 避免出现错误的可行解
- 回溯往往会结合递归，递归要有返回条件
最后值得一提，回溯算法只适合搜索空间不大的场景，一般leetcode使用回溯求解场景，最后一般限制列表长度在20以下，这是因为当长度增大时，时间求解复杂度呈现的是指数级增长，所以不适合求解长度过长的问题。
7 实际问题
7.1 不含重复元素求子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
链接：https://leetcode-cn.com/problems/subsets
分析与代码
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
def search(i, sol):
"""
:i: 代表回溯检查点
:sol: [0,i] 区间时解部分结构
"""
res.append(sol)
for j in range(i, n):
search(j + 1, sol + [nums[j]])
search(0, [])
return res
上面代码比较容易犯错地方：sol + [nums[j]]，不能写为：sol.append(nums[j])
原因是sol是search方法的参数，在for j in range(i, n)时，从j到j+1搜索时，sol要维持不变，不能出现元素增加。
7.2 含重复元素求子集
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
链接：https://leetcode-cn.com/problems/subsets-ii
分析与代码
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
nums.sort()
def search(i, sol):
if sol not in res:
res.append(sol)
for j in range(i, n):
search(j + 1, sol + [nums[j]])
search(0, [])
return res
与求解不含重复元素求子集的框架相似，收集解时不能出现重复，所以在search前先排序。解决下面情况，如搜索下面列表的子集时
[4,4,4,1,4]
不能出现这种重复解
[4,4,4,1]
[4,4,1,4]
7.3 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
链接：https://leetcode-cn.com/problems/word-search
分析与代码
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if len(board) == 0:
return False
row_len, col_len, word_len = len(board), len(board[0]), len(word)
def search(i, j, root):
"""
i,j is index in board
决策i,j是否放入root, 如果放入再进一步搜索
如果不能放入root，也就完全没必要进一步搜索
"""
k, tmp = len(root), root
if k == word_len:
return True
if i < 0 or j < 0 or i >= row_len or j >= col_len:
return False
if (i, j) not in root and board[i][j] == word[k]:
path = root + [(i, j)]
if (i - 1, j) not in root and search(i - 1, j, path):
return True
if (i + 1, j) not in root and search(i + 1, j, path):
return True
if (i, j - 1) not in root and search(i, j - 1, path):
return True
if (i, j + 1) not in root and search(i, j + 1, path):
return True
else: # 剪枝
return False
for row in range(0, row_len):
for col in range(0, col_len):
if search(row, col, []):
return True
return False
大家在看
