回溯算法详解

算法 回溯 搜索

学习提示

回溯算法是解决组合优化问题的强大工具。建议先掌握递归，再学习回溯。预计学习时间 2 周。

一、什么是回溯算法？ 🔙

回溯算法（Backtracking）是一种系统地搜索问题解空间的算法，它通过逐步构建候选解，并在发现当前路径无法得到有效解时"回溯"到上一步。

核心思想

回溯 vs 暴力搜索

特性 暴力搜索 回溯算法
搜索方式 枚举所有可能 智能剪枝
效率 低（指数级） 较高（剪枝后）
实现难度 简单 中等
适用场景 小规模问题 组合优化问题
形象比喻

回溯就像走迷宫：

二、回溯算法模板 📐

掌握回溯的关键是理解通用模板。

标准模板

回溯算法通用模板 
def backtrack(路径, 选择列表):
    """
    回溯算法模板
    :param 路径: 已经做出的选择
    :param 选择列表: 当前可以做的选择
    """
    # 终止条件：找到完整解
    if 满足结束条件:
        记录结果
        return
    
    # 遍历所有选择
    for 选择 in 选择列表:
        # 做选择
        做选择(选择)
        
        # 进入下一层决策树
        backtrack(路径, 新的选择列表)
        
        # 撤销选择（回溯）
        撤销选择(选择)

模板解析

三步走策略
1. 做选择：将当前选择加入路径 2. 递归：进入下一层，继续选择 3. 撤销：从路径中移除选择，尝试下一个 这三步构成了回溯的核心循环。

三、经典回溯问题 🏆

1. 全排列问题

问题：给定一个不含重复数字的数组，返回其所有可能的全排列。

全排列实现 
def permute(nums):
    """
    全排列 - 回溯算法
    :param nums: 输入数组
    :return: 所有排列的列表
    """
    result = []
    
    def backtrack(path, used):
        # 终止条件：路径长度等于数组长度
        if len(path) == len(nums):
            result.append(path[:])  # 添加副本
            return
        
        # 遍历所有数字
        for i in range(len(nums)):
            # 跳过已使用的数字
            if used[i]:
                continue
            
            # 做选择
            path.append(nums[i])
            used[i] = True
            
            # 递归
            backtrack(path, used)
            
            # 撤销选择
            path.pop()
            used[i] = False
    
    backtrack([], [False] * len(nums))
    return result

# 测试
print(permute([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

时间复杂度：O(n × n!)，n! 种排列，每种需要 O(n) 复制

2. 子集问题

问题：给定一个整数数组，返回该数组所有可能的子集（幂集）。

子集问题 
def subsets(nums):
    """
    子集问题 - 回溯算法
    :param nums: 输入数组
    :return: 所有子集的列表
    """
    result = []
    
    def backtrack(start, path):
        # 每个节点都是一个有效子集
        result.append(path[:])
        
        # 从 start 开始遍历，避免重复
        for i in range(start, len(nums)):
            # 做选择
            path.append(nums[i])
            
            # 递归（注意传入 i+1，不是 start+1）
            backtrack(i + 1, path)
            
            # 撤销选择
            path.pop()
    
    backtrack(0, [])
    return result

# 测试
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

关键点：使用 start 参数避免重复子集

3. N 皇后问题

问题：在 N×N 的棋盘上放置 N 个皇后，使得它们互不攻击。

N 皇后问题 
def solve_n_queens(n):
    """
    N 皇后问题 - 回溯算法
    :param n: 棋盘大小和皇后数量
    :return: 所有解的列表
    """
    result = []
    board = [-1] * n  # board[i] = j 表示第 i 行皇后在第 j 列
    
    def is_safe(row, col):
        """检查在 (row, col) 放置皇后是否安全"""
        for i in range(row):
            # 检查列冲突
            if board[i] == col:
                return False
            # 检查对角线冲突
            if abs(board[i] - col) == abs(i - row):
                return False
        return True
    
    def backtrack(row):
        # 终止条件：所有皇后都放置完毕
        if row == n:
            # 转换为字符串格式
            solution = []
            for i in range(n):
                line = '.' * board[i] + 'Q' + '.' * (n - board[i] - 1)
                solution.append(line)
            result.append(solution)
            return
        
        # 尝试每一列
        for col in range(n):
            if is_safe(row, col):
                # 做选择
                board[row] = col
                
                # 递归
                backtrack(row + 1)
                
                # 撤销选择（自动完成，因为会被覆盖）
    
    backtrack(0)
    return result

# 测试
solutions = solve_n_queens(4)
print(f"4 皇后有 {len(solutions)} 种解法")
for sol in solutions:
    for line in sol:
        print(line)
    print()

优化技巧：

4. 括号生成

问题：数字 n 代表生成括号的对数，设计一个函数用于生成所有可能的并且有效的括号组合。

python 
def generate_parentheses(n):
    """
    括号生成 - 回溯算法
    :param n: 括号对数
    :return: 所有有效括号组合
    """
    result = []
    
    def backtrack(current, open_count, close_count):
        # 终止条件：生成了 2n 个字符
        if len(current) == 2 * n:
            result.append(current)
            return
        
        # 可以添加左括号（如果还没用完）
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)
        
        # 可以添加右括号（如果右括号少于左括号）
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)
    
    backtrack('', 0, 0)
    return result

# 测试
print(generate_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

剪枝策略：

四、回溯的优化技巧 ⚡

1. 剪枝优化

剪枝是回溯算法的核心优化手段，提前排除不可能的路径。

常见剪枝策略
可行性剪枝：当前选择违反约束，立即回溯 最优性剪枝：当前路径不可能优于已知最优解，剪掉 对称性剪枝：利用问题对称性，避免重复搜索

示例：组合总和问题

python 
def combination_sum(candidates, target):
    """
    组合总和 - 带剪枝的回溯
    :param candidates: 候选数字
    :param target: 目标和
    :return: 所有组合
    """
    result = []
    candidates.sort()  # 排序便于剪枝
    
    def backtrack(start, path, remaining):
        # 终止条件
        if remaining == 0:
            result.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            # 剪枝：如果当前数字已经大于剩余值，后面的也不用看了
            if candidates[i] > remaining:
                break
            
            # 做选择
            path.append(candidates[i])
            
            # 递归（注意传入 i，因为可以重复使用）
            backtrack(i, path, remaining - candidates[i])
            
            # 撤销选择
            path.pop()
    
    backtrack(0, [], target)
    return result

# 测试
print(combination_sum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]

2. 记忆化优化

对于有重叠子问题的回溯，可以使用记忆化。

注意

纯回溯通常不使用记忆化，因为每个路径都是唯一的。但如果存在重复子状态，可以考虑 DP。

python
def iterative_deepening(max_depth):
    for depth in range(1, max_depth + 1):
        result = dfs_with_limit(depth)
        if result:
            return result
    return None

3. 迭代加深

限制搜索深度，逐步增加深度限制。

五、回溯的应用场景 💼

场景一：密码破解

回溯可以用于暴力破解密码（仅限合法的安全测试）：

道德提醒

仅在授权范围内使用回溯进行安全测试，未经授权的系统入侵是违法行为。

场景二：数独求解

数独是回溯的经典应用：

数独求解器简化版 
def solve_sudoku(board):
    """
    数独求解 - 回溯算法
    :param board: 9x9 数独棋盘，0 表示空格
    :return: 是否找到解
    """
    def is_valid(board, row, col, num):
        """检查在 (row, col) 放置 num 是否合法"""
        # 检查行
        if num in board[row]:
            return False
        
        # 检查列
        if num in [board[i][col] for i in range(9)]:
            return False
        
        # 检查 3x3 宫格
        start_row, start_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(start_row, start_row + 3):
            for j in range(start_col, start_col + 3):
                if board[i][j] == num:
                    return False
        
        return True
    
    def backtrack():
        # 找到第一个空格
        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    # 尝试 1-9
                    for num in range(1, 10):
                        if is_valid(board, i, j, num):
                            board[i][j] = num
                            
                            if backtrack():
                                return True
                            
                            board[i][j] = 0  # 回溯
                    
                    return False  # 无解
        
        return True  # 所有格子都填满了
    
    backtrack()
    return board

场景三：图的着色问题

问题：给定一个无向图和 m 种颜色，为每个顶点着色，使得相邻顶点颜色不同。

应用领域：

场景四：单词搜索

在二维网格中搜索单词：

python 
def exist(board, word):
    """
    单词搜索 - 回溯算法
    :param board: 二维字符网格
    :param word: 要搜索的单词
    :return: 是否存在
    """
    rows, cols = len(board), len(board[0])
    
    def backtrack(r, c, index):
        # 终止条件：找到完整单词
        if index == len(word):
            return True
        
        # 边界检查和字符匹配
        if (r < 0 or r >= rows or c < 0 or c >= cols or 
            board[r][c] != word[index]):
            return False
        
        # 标记为已访问
        temp = board[r][c]
        board[r][c] = '#'
        
        # 四个方向搜索
        found = (backtrack(r+1, c, index+1) or
                backtrack(r-1, c, index+1) or
                backtrack(r, c+1, index+1) or
                backtrack(r, c-1, index+1))
        
        # 恢复
        board[r][c] = temp
        
        return found
    
    # 从每个位置开始搜索
    for i in range(rows):
        for j in range(cols):
            if backtrack(i, j, 0):
                return True
    
    return False

六、回溯 vs 其他算法 ⚖️

算法 搜索方式 适用场景 时间复杂度
回溯 DFS + 剪枝 组合优化 指数级（剪枝后改善）
BFS 层次遍历 最短路径 O(V + E)
动态规划 表格填充 重叠子问题 多项式级
贪心 局部最优 满足贪心性质 通常较低

选择指南

七、常见问题与技巧 💡

如何避免重复解？

方法一：排序 + 跳过相同元素

python
if i > start and candidates[i] == candidates[i-1]:
    continue

方法二：使用集合去重

python
result = list(set(result))

方法三：控制搜索起点（如子集问题中的 start 参数）

如何处理大规模数据？

优化策略：

  1. 加强剪枝条件
  2. 使用启发式排序
  3. 并行化处理
  4. 考虑近似算法

如果回溯仍然太慢，可能需要重新思考算法选择。

回溯的空间复杂度？

主要消耗：

  • 递归调用栈：O(n)，n 为最大深度
  • 路径存储：O(n)
  • 结果存储：取决于解的数量

总空间复杂度：O(n + 结果大小)

如何调试回溯代码？

调试技巧：

  1. 打印每一步的选择和回溯
  2. 可视化搜索树
  3. 小规模测试
  4. 添加计数器统计调用次数
python
call_count = 0
def backtrack(...):
    global call_count
    call_count += 1
    print(f"Call {call_count}: path={path}")

八、练习与挑战 🏆

推荐练习题

LeetCode 46. 全排列

给定一个不含重复数字的数组，返回其所有可能的全排列。 难度：⭐⭐ 中等 通过率：78%

LeetCode 78. 子集

给你一个整数数组，返回该数组所有可能的子集（幂集）。 难度：⭐⭐ 中等 通过率：82%

LeetCode 39. 组合总和

找出数组中所有可以使数字和为目标数的组合。 难度：⭐⭐ 中等 通过率：72%

LeetCode 51. N 皇后

在 N×N 的棋盘上放置 N 个皇后，使其互不攻击。 难度：⭐⭐⭐ 困难 通过率：62%

九、学习路径建议 🗺️

第1-3天
基础理解
掌握回溯模板，实现全排列和子集问题。
第4-7天
经典问题
深入学习 N 皇后、括号生成等经典问题。
第8-10天
剪枝优化
学习各种剪枝技巧，提升算法效率。
第11-14天
实战练习
完成 LeetCode 回溯专题，至少 15 道题目。

十、总结 🎯

回溯算法是解决组合优化问题的强大工具，虽然时间复杂度较高，但通过剪枝可以大幅提升效率。

掌握回溯艺术

回溯需要大量练习才能熟练掌握。坚持下去，你会发现自己解决复杂问题的能力大幅提升！

查看回溯专题练习 下载完整代码

© 2026 AI未来实验室 · 用 AI 探索无限可能
站点地图 | Robots.txt | 关于