回溯算法

回溯算法（Backtracking）是一种通过递归或迭代逐步构建候选解，并在发现当前候选解无法满足条件时回退（“回溯”）的通用算法。它常用于解决组合问题（如排列、子集、分割）和决策问题（如数独、N皇后），其核心思想是“试探与撤销”。

基本思想

回溯算法可视为对解空间的深度优先搜索（DFS），其执行过程如下：

1. 按特定规则逐步构建候选解。
2. 若当前步骤满足约束条件，则继续向下递归。
3. 若当前路径无法得到有效解，则回退到上一步（撤销选择），尝试其他可能性。

数学描述：设解为向量 $\mathbf{𝐱}=(x_1,x_2,\dots ,x_n)$，回溯算法通过以下步骤搜索解空间： $\{\begin{array}{l}\text{选择 }{x}_k\text{ 的可能值}\\ \text{验证约束条件 }C(\mathbf{𝐱})\\ \text{若满足，则递归处理 }{x}_{k+1}\\ \text{否则回溯并尝试其他值}\end{array}$

算法框架

以下是回溯算法的通用伪代码框架：

def backtrack(路径, 选择列表):
    if 满足终止条件:
        记录结果
        return
    
    for 选择 in 选择列表:
        做出选择
        backtrack(新路径, 新选择列表)  # 递归
        撤销选择  # 回溯

关键步骤

1. 路径：已做出的选择序列。 2. 选择列表：当前可用的选项。 3. 终止条件：到达决策树底层时的判断逻辑。

示例：全排列问题

给定不重复数字的数组，返回所有可能的排列。

输入与输出

输入: [1, 2, 3]
输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Python实现

def permute(nums):
    res = []
    
    def backtrack(path, remaining):
        if not remaining:
            res.append(path.copy())
            return
        
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()  # 撤销选择
    
    backtrack([], nums)
    return res

执行过程分析

graph TD A[开始: []] --> B[选择1] B --> C[选择2] C --> D[选择3] --> E[记录[1,2,3]] D --> F[回溯到选择2] C --> G[选择3] --> H[记录[1,3,2]] B --> I[选择2] I --> J[选择1] --> K[记录[2,1,3]] J --> L[选择3] --> M[记录[2,3,1]] A --> N[选择2] N --> O[...] # 省略部分分支

复杂度分析

回溯算法的时间复杂度通常较高，因其需遍历解空间：

• 全排列问题：$O(n\times n!)$（共有$n!$个解，每个解需$O(n)$时间生成）
• 空间复杂度：$O(n)$（递归栈深度）

优化技巧

1. 剪枝：提前终止不符合约束的分支（如N皇后问题中跳过冲突位置）。 2. 记忆化：存储已计算状态避免重复（如含重复元素的排列问题）。 3. 迭代实现：用栈模拟递归减少系统开销。

实际应用案例

案例1：数独求解

使用回溯算法填充数字，若冲突则回退：

def solveSudoku(board):
    def isValid(row, col, num):
        # 检查行、列、3x3宫格
        pass
    
    def backtrack():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if isValid(i, j, num):
                            board[i][j] = num
                            if backtrack(): return True
                            board[i][j] = '.'  # 回溯
                    return False
        return True
    
    backtrack()

案例2：子集问题

生成数组的所有子集（幂集）：

def subsets(nums):
    res = []
    
    def backtrack(start, path):
        res.append(path.copy())
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return res

总结

回溯算法通过系统性地尝试和回退寻找解，适合解决组合爆炸类问题。掌握其核心框架和剪枝技巧可显著提升解题效率。建议通过LeetCode（如46、51、78题）进行实战练习。