「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。回溯算法通常采用“深度优先搜索”来遍历解空间。
框架代码(函数)
def is_solution(state: list[TreeNode]) -> bool: """ 判断当前状态是否为解""" return None def record_solution(state: list[TreeNode], res: list[list[TreeNode]]): """ 记录解""" pass def is_valid(state: list[TreeNode], choice: TreeNode) -> bool: """ 判断在当前状态下，该选择是否合法""" return None def make_choice(state: list[TreeNode], choice: TreeNode): """ 更新状态""" pass def undo_choice(state: list[TreeNode], choice: TreeNode): """ 恢复状态""" pass def backtrack(state: State, choices: list[choice], res: list[state]): """ 回溯算法框架""" # 判断是否为解 if is_solution(state): # 记录解 record_solution(state, res) # 停止继续搜索 return # 遍历所有选择 for choice in choices: # 剪枝：判断选择是否合法 if is_valid(state, choice): # 尝试：做出选择，更新状态 make_choice(state, choice) backtrack(state, choices, res) # 回退：撤销选择，恢复到之前的状态 undo_choice(state, choice)
框架代码(类)
class TrackBack: def __init__(self, choises) -> None: self.state = [] self.choices = [choises] self.res = [] self.backtrack(self.state, self.choices, self.res) def is_solution(self): return self.state and self.state[-1].val == 7 def record_solution(self): self.res.append([s.val for s in self.state]) def is_valid(self, choice): return choice is not None and choice.val != 3 def make_choice(self, choice): self.state.append(choice) def undo_choice(self): self.state.pop() def backtrack(self, state, choices, res): if self.is_solution(): self.record_solution() for choice in choices: if self.is_valid(choice): self.make_choice(choice) self.backtrack(state, [choice.left, choice.right], res) self.undo_choice()
优势与局限性
回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优势在于它能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。
- 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。
- 空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间需求可能会变得很大。
即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何进行效率优化，常见的效率优化方法有两种。 - 剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。
- 启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径。
回溯典型例题
回溯算法可用于解决许多搜索问题、约束满足问题和组合优化问题。
- 搜索问题：这类问题的目标是找到满足特定条件的解决方案。
- 全排列问题：给定一个集合，求出其所有可能的排列组合。
- 子集和问题：给定一个集合和一个目标和，找到集合中所有和为目标和的子集。
- 汉诺塔问题：给定三个柱子和一系列大小不同的圆盘，要求将所有圆盘从一个柱子移动到另一个柱子，每次只能移动一个圆盘，且不能将大圆盘放在小圆盘上。
- 约束满足问题：这类问题的目标是找到满足所有约束条件的解。
- 𝑛 皇后：在 𝑛 × 𝑛 的棋盘上放置 𝑛 个皇后，使得它们互不攻击。
- 数独：在 9 × 9 的网格中填入数字 1 ~ 9 ，使得每行、每列和每个 3 × 3 子网格中的数字不重复。
- 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。
- 组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。
- 0‑1 背包问题：给定一组物品和一个背包，每个物品有一定的价值和重量，要求在背包容量限制内，选择物品使得总价值最大。
- 旅行商问题：在一个图中，从一个点出发，访问所有其他点恰好一次后返回起点，求最短路径。
- 最大团问题：给定一个无向图，找到最大的完全子图，即子图中的任意两个顶点之间都有边相连。
- 请注意，对于许多组合优化问题，回溯都不是最优解决方案。
- 0‑1 背包问题通常使用动态规划解决，以达到更高的时间效率。
- 旅行商是一个著名的 NP‑Hard 问题，常用解法有遗传算法和蚁群算法等。
- 最大团问题是图论中的一个经典问题，可用贪心等启发式算法来解决。
全排列问题(考虑重复选择剪枝和相等元素剪枝)
全排列问题是回溯算法的一个典型应用。它的定义是在给定一个集合（如一个数组或字符串）的情况下，找出这个集合中元素的所有可能的排列。
class TrackBack: def __init__(self, choises) -> None: self.state = [] self.choices = choises self.res = [] self.backtrack(self.state, self.choices, [False] * len(self.choices), self.res) def is_solution(self): return self.state and len(self.state) == len(self.choices) def record_solution(self): self.res.append(self.state.copy()) def is_valid(self, ix, selected, choice, duplicated): return not selected[ix] and choice not in duplicated def make_choice(self, choice): self.state.append(choice) def undo_choice(self): self.state.pop() def backtrack(self, state, choices, selected, res): if self.is_solution(): self.record_solution() duplicated = set() for ix, choice in enumerate(choices): if self.is_valid(ix, selected, choice, duplicated): duplicated.add(choice) selected[ix] = True self.make_choice(choice) self.backtrack(state, choices, selected, res) selected[ix] = False self.undo_choice()
请注意，虽然 selected 和 duplicated 都用作剪枝，但两者的目标是不同的。
- 重复选择剪枝：整个搜索过程中只有一个 selected 。它记录的是当前状态中包含哪些元素，作用是避免某个元素在 state 中重复出现。
- 相等元素剪枝：每轮选择（即每个开启的 backtrack 函数）都包含一个 duplicated 。它记录的是在遍历中哪些元素已被选择过，作用是保证相等元素只被选择一次
子集和问题
无重复元素的情况
Q:给定一个正整数数组 nums 和一个目标正整数 target ，请找出所有可能的组合，使得组合中的元素和等于 target 。给定数组无重复元素，每个元素可以被选取多次。请以列表形式返回这些组合，列表中不应包含重复组合。
例如，输入集合 {3, 4, 5} 和目标整数 9 ，解为 {3, 3, 3}, {4, 5} 。需要注意以下两点。
- 输入集合中的元素可以被无限次重复选取。
- 子集是不区分元素顺序的，比如 {4, 5} 和 {5, 4} 是同一个子集。
class TrackBack: def __init__(self, choices, target) -> None: self.state = [] self.choices = choices self.res = [] self.target = target self.backtrack(self.state, 0, self.choices, self.res) def is_solution(self): return sum(self.state) == self.target def record_solution(self): self.res.append(self.state.copy()) def is_valid(self, choice): return sum(self.state) < self.target def make_choice(self, choice): self.state.append(choice) def undo_choice(self): self.state.pop() def backtrack(self, state, start, choices, res): if self.is_solution(): self.record_solution() for ix in range(start, len(choices)): if self.is_valid(choices[ix]): self.make_choice(choices[ix]) print(self.state) self.backtrack(state, ix, choices, res) self.undo_choice()
考虑重复元素的情况
Q:给定一个正整数数组 nums 和一个目标正整数 target ，请找出所有可能的组合，使得组合中的元素和等于 target 。给定数组可能包含重复元素，每个元素只可被选择一次。请以列表形式返回这些组合，列表中不应包含重复组合。
class TrackBack: def __init__(self, choices, target) -> None: self.state = [] self.choices = choices self.res = [] self.target = target self.backtrack(self.state, self.target, 0, [False]*len(self.choices), self.choices, self.res) def is_solution(self, target): return target == 0 def record_solution(self): self.res.append(self.state.copy()) def is_valid(self, ix, start, selected, choices): if ix > start and choices[ix] == choices[ix-1] : return False else: return selected[ix] == False def make_choice(self, choice): self.state.append(choice) def undo_choice(self): self.state.pop() def backtrack(self, state, target, start, selected, choices, res): if self.is_solution(target): self.record_solution() for ix in range(start, len(choices)): if self.is_valid(ix, start, selected, choices): self.make_choice(choices[ix]) selected[ix] = True self.backtrack(state, target-choices[ix], ix+1, selected, choices, res) selected[ix] = False self.undo_choice()
N皇后问题
Q:根据国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。给定 𝑛个皇后和一个 𝑛 × 𝑛 大小的棋盘，寻找使得所有皇后之间无法相互攻击的摆放方案。
class TrackBack: def __init__(self, n) -> None: diag1 = [False] * (n*2-1) diag2 = [False] * (n*2-1) cols = [False] * n self.state = [['#'] * n for _ in range(n)] self.res = [] self.dfs(n, 0, diag1, diag2, cols) def dfs(self, n, row, diag1, diag2, cols): if row == n: self.res.append([list(row) for row in self.state]) return None for col in range(n): if row < n: d_1 = col + row d_2 = col - row + n - 1 if diag1[d_1] == False and diag2[d_2] == False and cols[col] == False: self.state[row][col] = 'Q' cols[col] = diag1[d_1] = diag2[d_2] = True self.dfs(n, row+1, diag1, diag2, cols) self.state[row][col] = '#' cols[col] = diag1[d_1] = diag2[d_2] = False
重点回顾
- 回溯算法本质是穷举法，通过对解空间进行深度优先遍历来寻找符合条件的解。在搜索过程中，遇到满足条件的解则记录，直至找到所有解或遍历完成后结束。
- 回溯算法的搜索过程包括尝试与回退两个部分。它通过深度优先搜索来尝试各种选择，当遇到不满足约束条件的情况时，则撤销上一步的选择，退回到之前的状态，并继续尝试其他选择。尝试与回退是两个方向相反的操作。
- 回溯问题通常包含多个约束条件，它们可用于实现剪枝操作。剪枝可以提前结束不必要的搜索分支，大幅提升搜索效率。
- 回溯算法主要可用于解决搜索问题和约束满足问题。组合优化问题虽然可以用回溯算法解决，但往往存在更高效率或更好效果的解法。
- 全排列问题旨在搜索给定集合的所有可能的排列。我们借助一个数组来记录每个元素是否被选择，剪枝掉重复选择同一元素的搜索分支，确保每个元素只被选择一次。
- 在全排列问题中，如果集合中存在重复元素，则最终结果会出现重复排列。我们需要约束相等元素在每轮中只能被选择一次，这通常借助一个哈希表来实现。
- 子集和问题的目标是在给定集合中找到和为目标值的所有子集。集合不区分元素顺序，而搜索过程会输出所有顺序的结果，产生重复子集。我们在回溯前将数据进行排序，并设置一个变量来指示每一轮的遍历起点，从而将生成重复子集的搜索分支进行剪枝。
- 对于子集和问题，数组中的相等元素会产生重复集合。我们利用数组已排序的前置条件，通过判断相邻元素是否相等实现剪枝，从而确保相等元素在每轮中只能被选中一次。
- 𝑛皇后旨在寻找将 𝑛 个皇后放置到 𝑛 × 𝑛 尺寸棋盘上的方案，要求所有皇后两两之间无法攻击对方。该问题的约束条件有行约束、列约束、主对角线和副对角线约束。为满足行约束，我们采用按行放置的策略，保证每一行放置一个皇后。
- 列约束和对角线约束的处理方式类似。对于列约束，我们利用一个数组来记录每一列是否有皇后，从而指示选中的格子是否合法。对于对角线约束，我们借助两个数组来分别记录该主、副对角线是否存在皇后；难点在于找处在到同一主（副）对角线上格子满足的行列索引规律。
