回溯算法题模板与实战详解

回溯算法模板

回溯算法的一般框架如下：

def backtrack(当前状态, 选择列表):# 基准情形：如果满足结束条件，则处理当前状态，如打印结果或添加到结果列表if 满足结束条件:处理当前状态return# 选择：基于当前状态做出选择，进入下一层决策树for 选择 in 选择列表:# 做出选择make_choice(当前状态, 选择)# 递归：在新状态下继续搜索backtrack(当前状态, 选择列表)# 撤销选择：回到上一层决策树，撤销之前的选择undo_choice(当前状态, 选择)

实战详解

全排列问题

问题描述：给定一个不含重复数字的整型数组 nums，返回它所有可能的全排列。

解法思路：

• 初始化：定义一个空列表 res 用来存储结果，以及一个列表 track 用来记录当前路径。
• 终止条件：当 track 的长度等于 nums 的长度时，说明已找到一个排列，将其添加到结果列表 res 中。
• 选择列表：对于每个数字，可以选择或不选择，但由于不能重复选择，故直接遍历 nums 即可。
• 递归调用：在每次循环中选择一个数字加入 track，然后递归调用 backtrack 函数。
• 回溯：在递归返回后，将刚刚加入的数字从 track 中移除，以便于进行下一个数字的选择。

Python代码示例：

def permute(nums):def backtrack(first = 0):# 如果路径长度等于nums的长度，说明已经找到一个解if first == n:  res.append(track[:])returnfor i in range(first, n):# 动态维护数组nums[first], nums[i] = nums[i], nums[first]track.append(nums[first])# 继续递归构造下一个数backtrack(first + 1)# 撤销操作track.pop()nums[first], nums[i] = nums[i], nums[first]n = len(nums)res = []track = []backtrack()return res

N皇后问题

问题描述：在 n × n 的棋盘上放置 n 个皇后，使得任意两个皇后都不在同一行、同一列以及不在对角线上。

解法思路：

• 初始化：定义棋盘 board 和结果列表 res。
• 终止条件：当所有皇后都被放置完毕，即 row 等于 n 时，将当前棋盘状态加入 res。
• 选择列表：在每一行，可以选择每一列放置皇后，但需通过 isValid 函数确保不冲突。
• 递归调用：在每行选择一个合法列放置皇后后，递归进入下一行。
• 回溯：如果当前行无法放置皇后，撤销选择，尝试下一列。

Python代码示例：

def solveNQueens(n):def isValid(row, col):# 检查列是否有皇后冲突for i in range(row):if board[i] == col or \board[i] - i == col - row or \board[i] + i == col + row:return Falsereturn Truedef backtrack(row=0):if row == n:res.append(board[:])returnfor col in range(n):if isValid(row, col):board[row] = colbacktrack(row + 1)board = [-1]*nres = []backtrack()return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in res]

以上两个实例展示了回溯算法在实际问题中的应用，通过不断尝试、验证、回溯，最终找出所有符合条件的解。在解决此类问题时，正确管理状态、合理设计剪枝条件是提高算法效率的关键。

接下来让我们看看回溯算法在其他经典问题上的应用：“组合总和”问题和“子集问题”。

组合总和问题

问题描述：给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。候选数字可以无限制重复被选取。

解法思路：

• 初始化：定义结果列表 res，路径列表 path，以及起始索引 start。
• 终止条件：当路径的和等于目标值时，将路径加入结果列表。
• 选择列表：从当前起始索引开始，遍历数组，可以选择当前数多次（通过递归调用时保持起始索引不变实现）。
• 递归调用：在当前路径的和未超过目标值时，继续向下一层决策树探索。
• 回溯：在递归返回后，从路径中移除最后一个添加的数，相当于回溯至上一步，改变选择。

Python代码示例：

def combinationSum(candidates, target):def backtrack(start, target, path):if target == 0:res.append(path)returnif start >= len(candidates) or target < candidates[start]:returnfor i in range(start, len(candidates)):backtrack(i, target - candidates[i], path + [candidates[i]])res = []candidates.sort()  # 排序可以提前剪枝backtrack(0, target, [])return res

子集问题

问题描述：给定一个不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

解法思路：

• 初始化：定义结果列表 res 和路径列表 track。
• 终止条件：当遍历完整个数组时，将当前路径加入结果列表。
• 选择列表：对于数组中的每个元素，都有两种选择，选或不选。
• 递归调用：递归进入下一层时，将当前元素加入路径；递归返回时，从路径中移除当前元素。
• 回溯：通过在递归返回时从路径中移除最后一个添加的元素来实现回溯。

Python代码示例：

def subsets(nums):def backtrack(start, path):res.append(path[:])  # 拷贝当前路径并加入结果列表for i in range(start, len(nums)):path.append(nums[i])  # 选择当前元素backtrack(i + 1, path)  # 递归进入下一层path.pop()  # 回溯，撤销选择res = []backtrack(0, [])  # 从第一个元素开始考虑return res

通过这些例子，我们可以看到回溯算法的核心思想在于深度优先探索解空间，并通过剪枝和回溯策略有效减少不必要的搜索，从而高效地解决问题。理解这些基本框架和思想后，你就能更好地应对各种回溯算法相关的题目了。

再增加两个回溯算法在另外两个经典问题上的应用：“括号生成”和“单词搜索”，让大家理解更深入些

括号生成问题

问题描述：给定一个整数 n，生成所有合法的括号组合，合法的括号组合需要满足以下条件：左括号必须以正确的顺序闭合，右括号也有正确的顺序。

解法思路：

• 初始化：定义结果列表 res 和路径字符串 curr。
• 终止条件：当路径字符串的长度为 2*n 时，检查是否合法，如果合法则加入结果列表。
• 选择列表：在任何时候，都可以选择添加一个开括号 ‘(’ 或者在开括号数量多于闭括号数量时添加一个闭括号 ‘)’。
• 递归调用：在添加一个符号后，递归生成剩余的括号组合。
• 回溯：在递归返回后，从路径中移除最后添加的括号，恢复到上一步的状态。

Python代码示例：

def generateParenthesis(n):def backtrack(openN, closeN, curr):if openN == closeN == n:res.append(curr)returnif openN < n:backtrack(openN + 1, closeN, curr + '(')if closeN < openN:backtrack(openN, closeN + 1, curr + ')')res = []backtrack(0, 0, '')return res

单词搜索问题

问题描述：给定一个二维字符网格 board 和一个单词 word，判断单词 word 是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许重复使用。

解法思路：

• 初始化：定义方向列表，用于表示上下左右四个移动方向，以及访问矩阵 visited 记录哪些单元格已经被访问过。
• 终止条件：当搜索到单词的最后一个字符时，说明找到了合法路径。
• 选择列表：对于当前位置，可以向四个方向（上、下、左、右）移动。
• 递归调用：在新位置上继续搜索下一个字符，同时标记当前单元格为已访问。
• 回溯：在递归返回后，需要取消当前单元格的访问标记，以便于其他路径的探索。

Python代码示例：

def exist(board, word):def dfs(i, j, k):if not 0 <= i < m or not 0 <= j < n or board[i][j] != word[k] or visited[i][j]:return Falseif k == len(word) - 1:return Truevisited[i][j] = Truefor dx, dy in directions:if dfs(i + dx, j + dy, k + 1):return Truevisited[i][j] = False  # 回溯return Falsem, n = len(board), len(board[0])directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]visited = [[False]*n for _ in range(m)]for i in range(m):for j in range(n):if dfs(i, j, 0):return Truereturn False

通过这些实例，我们可以进一步体会到回溯算法在解决具有多种可能性或组合问题时的强大之处。掌握这些典型应用，能帮助你在面对复杂问题时更加游刃有余。

————————————————

​最后我们放松一下眼睛