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

文章目录

- - 回溯算法模板
  - 实战详解
  - - 全排列问题
    - N皇后问题
  - 组合总和问题
  - 子集问题
  - 括号生成问题
  - 单词搜索问题

回溯算法是一种通过试错的方式来寻找问题解决方案的算法，常用于解决约束满足问题、组合优化问题和排列组合问题。其核心思想是深度优先搜索(DFS)与剪枝策略的结合，即通过探索问题的解空间树，当发现当前路径不符合要求时及时“回溯”，撤销之前的部分决策，换一个分支继续搜索。

回溯算法模板

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

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[:])
            return
        for 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 False
        return True

    def backtrack(row=0):
        if row == n:
            res.append(board[:])
            return
        for col in range(n):
            if isValid(row, col):
                board[row] = col
                backtrack(row + 1)
    
    board = [-1]*n
    res = []
    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)
            return
        if start >= len(candidates) or target < candidates[start]:
            return
        
        for 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)
            return
        if 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 False
        if k == len(word) - 1:
            return True
        
        visited[i][j] = True
        for dx, dy in directions:
            if dfs(i + dx, j + dy, k + 1):
                return True
        visited[i][j] = False  # 回溯
        return False
    
    m, 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 True
    return False