算法-回溯思想

前言

回溯算法是一种通过递归试探所有可能解，并在遇到不满足条件的情况时回退（撤销选择）的算法思想。其核心在于系统性搜索解空间，并通过剪枝优化效率。以下是回溯思想的详细解析：

核心思想

试错与回退

回溯法通过逐步构建解，并在发现当前路径无法达到目标时，撤销最近的选择（回溯），尝试其他可能的分支。类似深度优先搜索（DFS），但强调状态的重置。

解空间树

将问题抽象为树形结构，每个节点代表一个决策状态，分支代表可能的选择，叶子节点为候选解。回溯法遍历这棵树，记录合法解。

算法框架

1
2
3
4
5
6
7
8
9
10

result = []
def backtrack(路径, 选择列表):
    if 满足终止条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        if 不满足剪枝条件:
            做选择（更新路径和选择列表）
            backtrack(新路径, 新选择列表)
            撤销选择（恢复路径和选择列表）

关键步骤

1. 路径：已做出的选择（如当前组合）。
2. 选择列表：当前可选的决策（如剩余未使用的元素）。
3. 终止条件：到达解空间树的叶子节点（如路径长度等于数组长度）。
4. 剪枝：提前跳过不满足条件的分支（如排除重复组合）。

经典问题与实例

1. 全排列（LeetCode 46）

   • 问题：生成数组的所有排列。
   • 回溯逻辑：每次选择一个未使用的数加入路径，递归处理剩余元素，回溯时撤销选择。
   • 剪枝：通过 visited 数组标记已选元素，避免重复选择。

2. 子集（LeetCode 78）

   • 问题：生成数组的所有子集。
   • 回溯逻辑：每个元素选择“加入”或“不加入”，通过索引控制顺序避免重复。

3. N皇后（LeetCode 51）

   • 问题：在 N×N 棋盘放置皇后，使其互不攻击。
   • 剪枝：检查当前放置位置是否与已存在的皇后冲突。

优化技巧

剪枝

可行性剪枝：提前终止不可能到达解的路径（如组合总和超过目标值）。
去重剪枝：排序后跳过相同元素（如子集II中避免重复子集）。

状态复用

通过索引传递而非复制新数组（如 start 参数控制选择范围）。

记忆化

结合哈希表记录中间状态，避免重复计算（如解决重复子问题）。

适用场景

• 组合、排列、子集类问题（穷举所有可能）。
• 分割问题（如分割回文串）。
• 棋盘问题（如N皇后、数独）。
• 需要记录路径的 DFS 场景。

后记

回溯法的本质是暴力搜索+剪枝，通过递归遍历解空间树，适时回退以探索所有分支。熟练掌握模板后，需结合具体问题设计路径记录、剪枝条件及状态管理策略。多练习经典题目（如LeetCode 46、39、78、51）能深化理解。