编辑“︁回溯算法”︁

{{Note|本条目介绍的是计算机科学中的'''回溯算法'''，适用于解决约束满足问题和组合优化问题。}}

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

== 基本思想 ==
回溯算法可视为对'''解空间的深度优先搜索'''（DFS），其执行过程如下：
# 按特定规则逐步构建候选解。
# 若当前步骤满足约束条件，则继续向下递归。
# 若当前路径无法得到有效解，则回退到上一步（撤销选择），尝试其他可能性。

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

== 算法框架 ==
以下是回溯算法的通用伪代码框架：
<syntaxhighlight lang="python">
def backtrack(路径, 选择列表):
    if 满足终止条件:
        记录结果
        return
    
    for 选择 in 选择列表:
        做出选择
        backtrack(新路径, 新选择列表)  # 递归
        撤销选择  # 回溯
</syntaxhighlight>

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

== 示例：全排列问题 ==
给定不重复数字的数组，返回所有可能的排列。

=== 输入与输出 ===
<syntaxhighlight lang="python">
输入: [1, 2, 3]
输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
</syntaxhighlight>

=== Python实现 ===
<syntaxhighlight lang="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
</syntaxhighlight>

=== 执行过程分析 ===
<mermaid>
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[...]  # 省略部分分支
</mermaid>

== 复杂度分析 ==
回溯算法的时间复杂度通常较高，因其需遍历解空间：
* 全排列问题：<math>O(n \times n!)</math>（共有<math>n!</math>个解，每个解需<math>O(n)</math>时间生成）
* 空间复杂度：<math>O(n)</math>（递归栈深度）

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

== 实际应用案例 ==
=== 案例1：数独求解 ===
使用回溯算法填充数字，若冲突则回退：
<syntaxhighlight lang="python">
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()
</syntaxhighlight>

=== 案例2：子集问题 ===
生成数组的所有子集（幂集）：
<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 常见问题 ==
{{Q&A
|问题1 = 回溯与DFS有何区别？
|答案1 = DFS是图遍历算法，回溯是应用DFS思想的解题框架，强调“状态回退”。
|问题2 = 何时使用回溯而非动态规划？
|答案2 = 当需要枚举所有可能解（而非最优解）时使用回溯；动态规划适合有重叠子问题的情况。
}}

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

{{Algorithm-stub}}

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:算法基础]]