设想你站在一座巨大迷宫的入口：每条走廊都连着新的岔路，每个岔路又分出更多岔路，而你根本没有完整地图。你会怎么做？聪明探险家的做法是：随身带一盒粉笔，选一条没走过的路前进，在走过的路口做记号；一旦走进死胡同，就顺着记号原路退回，擦掉记号，换下一条路再试。这套“走一路、记一路、撞墙回头换条路”的探险方法，就是计算机科学里大名鼎鼎的回溯算法（Backtracking）。它不靠运气，而是用一套简单规则，系统地把所有可能性都探索一遍。在 AI 算法面试中，回溯正是最高频的考点之一：排列、组合、子集、N 皇后……几乎每场算法轮都能遇到它的身影。本文就带你沿着探险家的路线，把回溯的核心原理、解题套路与面试策略一次讲透。

岗位关联

对 AI 从业者来说，回溯不仅是一道面试题，更是处理组合爆炸类工程问题的底层思维——掌握它，你就能在算法轮稳定拿分，并在特征搜索、资源调度等实际场景中游刃有余。

目录
  1. 可视化演示
  2. 核心原理：迷宫地图与探险规则
  3. 三大要素：岔路口的探险腰包
  4. 剪枝优化：危险警告牌与去重规则
  5. 经典题型：四种迷宫地形
  6. 复杂度分析：出发前数一数岔路
  7. 模板套路：探险手册的标准流程
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示回溯算法DFS决策树遍历（选择→探索→收集→回退）、N皇后棋盘约束检测与剪枝优化前后对比，通过多模式交互理解回溯核心原理。

本节配有交互动效（进入视口后自动加载，约 3KB）。

回溯算法决策树DFS遍历 选择(SEL)：在当前节点选择一个分支向下探索 探索(EXP)：递归深入直到叶子节点或死路 收集(COL)→回退(BTK)：保存结果并撤销选择 T(n) = O(b^d), b=分支因子，d=深度 回溯本质是带撤销的DFS搜索

核心原理：迷宫地图与探险规则

探险家进入迷宫后很快发现一个规律：迷宫虽大，但结构是分层的。入口是第一层，每条走廊通向第二层的某个岔口，再往深处是第三层、第四层……只要他肯一层层走下去，把每一层的每一条走廊都试一遍，他就能系统摸清全部路线。这棵“分层展开的选择树”，就是回溯眼中的世界。

在计算机里，这棵选择树被称为状态空间树（state-space tree）：根节点是初始状态，每往下走一层就代表做出一次选择，叶子节点是完整结果。回溯算法采用的遍历方式是深度优先（Depth-First Search，DFS）——选定一条分支后一口气走到最深处，直到无法继续，再退回上一层换另路。这正是探险家“一条路走到黑、撞墙再回头”的翻版。

从代码角度说，回溯 = DFS + 状态重置。程序会维护一个全局共享的路径列表，每深入一层就追加一个选择；一旦当前分支结束（遇到死胡同或已经走完），立刻撤销这个选择，让路径恢复原样，再尝试下一个候选。这种“进得来、出得去”的进退逻辑，用递归实现最为自然：递归调用栈的压栈与弹栈，恰好对应探险家的深入与折返。

探险家不需要预知整座迷宫，他按规则一个岔路一个岔路地试，最终羊皮纸上就画出了完整路线图。回溯的优雅之处正在于此：规则极简，却能系统驾驭指数级庞大的选择空间。

S=∑k=0nn!(n−k)!\displaystyle S = \sum_{k=0}^{n} \frac{n!}{(n-k)!}
这个公式数清了迷宫岔路的总数：第 k 层有 n!/(n-k)! 个节点，把所有层加起来，就是状态空间树的全部规模。
  1. 第 k 层岔路数从起点出发，第 k 层代表已经做出了 k 次选择，例如全排列中已经确定了前 k 个数字；该层共有 n!/(n-k)! 个节点。
    第 k 层节点数=n!(n−k)!\displaystyle \text{第 } k \text{ 层节点数} = \frac{n!}{(n-k)!}
  2. 阶乘的含义n! 表示 n 个元素“排到底”的全部顺序数，即从 n 一直乘到 1 的连乘结果。
    n!=n×(n−1)×(n−2)×⋯×1\displaystyle n! = n \times (n-1) \times (n-2) \times \cdots \times 1
  3. 选择逐步收缩前面已经选了 k 个元素后，剩余可排列的元素只剩 n-k 个，因此节点数等于 n! 除以 (n-k)!。
    n!(n−k)!=n(n−1)⋯(n−k+1)\displaystyle \frac{n!}{(n-k)!} = n(n-1) \cdots (n-k+1)
  4. 全迷宫求和把从第 0 层到第 n 层所有岔路口累加起来，得到整棵状态空间树的节点总数 S。
    S=1+n+n(n−1)+⋯+n!\displaystyle S = 1 + n + n(n-1) + \cdots + n!

三大要素：岔路口的探险腰包

每次站在岔路口，探险家都要清点腰包里的三样工具：一张列着“还没走过的走廊”的清单，一段粉笔画出来的已走路线，以及一张写着“什么才算到达终点”的判定卡。缺了清单，他会重复走老路；缺了路线，他会彻底迷路；缺了判定卡，他甚至不知道什么时候该停下。这三样工具，正是回溯算法的三大要素：选择列表、路径与终止条件。

对应到代码里：选择列表是“当前还能试的候选集合”；路径是“已经做出的选择序列”；终止条件是“路径满足题设要求”的判断逻辑。以全排列为例，选择列表是尚未使用的数字，路径是已经排好的前缀，终止条件则是路径长度等于数组长度 n。它们共同定义了一次回溯搜索的完整边界。

三要素缺一不可。许多新手只盯着终止条件，忘记维护选择列表，结果程序无限递归；也有人的路径记了却不撤销，导致兄弟分支被“陈年粉笔印”污染。腰包里的三样工具，必须一起用才走得通迷宫。

f(P)={记录答案 P,若 ∣P∣=n∑c∈C(P)f(P∪{c}),若 ∣P∣<n\displaystyle f(P) = \begin{cases} \text{记录答案 } P, & \text{若 } |P| = n \\[2pt] \sum_{c \in C(P)} f(P \cup \{c\}), & \text{若 } |P| < n \end{cases}
递归定义把“站在岔路口怎么办”写成了数学语言：路没走完就继续分叉，走完了就记录答案。
  1. 路径 PP 是当前已经做出的选择序列，等价于探险家粉笔记号连成的路线。
    P=[x1,x2,…,xk]\displaystyle P = [x_1, x_2, \dots, x_k]
  2. 终止分支当路径长度等于 n，即所有位置都被填满，说明已经到达出口，把 P 的记录当成一条答案保存。
    ∣P∣=n⇒record(P)\displaystyle |P| = n \Rightarrow \text{record}(P)
  3. 递归分支路径还没填满时，遍历选择列表 C(P) 中的每个候选 c，递归地继续构造更长的路径。
    ∣P∣<n⇒∑c∈C(P)f(P∪{c})\displaystyle |P| < n \Rightarrow \sum_{c \in C(P)} f(P \cup \{c\})
  4. 选择列表 C(P)尚未被使用、可以继续尝试的候选集合；不同题型里它的定义不同。
    C(P)={c∣c∉P}\displaystyle C(P) = \{ c \mid c \notin P \}

剪枝优化：危险警告牌与去重规则

老练的探险家会多带一样宝贝：一张“危险警告牌”地图。上面标着“此路尽头坍方”“那条走廊绕回起点”，遇到这样的路他看都不看直接跳过。回溯里的剪枝（pruning）就是给状态空间树挂警告牌——用题目的约束条件预先判断某个分支是否注定无解，是就直接砍掉，不再往下深入。

剪枝分为两类。第一类是可行性剪枝：例如求解 N 皇后时，如果某个位置放皇后会与已有的皇后冲突，就立刻放弃这个分支，而不是继续把棋盘填完再检查；第二类是重复去重剪枝：当输入数组含有重复元素时，相同元素在不同位置的排列会产出相同答案，必须靠剪枝去除。

以含重复元素的全排列为例，不去重会输出大量一模一样的排列。常规做法是先把数组排序，让相同元素相邻，然后在循环中加上“当前元素与上一个相同，且上一个元素尚未被使用，就跳过”的判断。这样重复分支被整支砍掉，答案数也会发生质变：

警告牌挂得越多，探险速度越快；剪枝做得越好，回溯才能从“暴力”升格为“优雅”。面试中，能在写代码前先说出“这道题哪里可以剪枝”的候选人，往往比闷头枚举的候选人得分高得多。

去重后排列数=n!m1! m2! ⋯ mk!\displaystyle \text{去重后排列数} = \frac{n!}{m_1!\, m_2!\, \cdots \, m_k!}
排序加剪枝之后，相同元素造成的重复排列被成批消除，答案数从 n! 骤降到公式所示的规模。
  1. 总排列数 n!不考虑重复时，n 个元素的排列一共有 n! 种，这是回溯搜索的上界。
    n!=n×(n−1)×⋯×1\displaystyle n! = n \times (n-1) \times \cdots \times 1
  2. 单类元素的冗余 m_i!如果第 i 种元素出现了 m_i 次，这 m_i 个相同元素之间互换位置并不会产生新的答案。
    mi!=第 i 类相同元素的个数阶乘\displaystyle m_i! = \text{第 } i \text{ 类相同元素的个数阶乘}
  3. 连乘去重把所有重复类别造成的冗余全部除掉，就得到真正不同的答案数。
    m1!×m2!×⋯×mk!=∏i=1kmi!\displaystyle m_1! \times m_2! \times \cdots \times m_k! = \prod_{i=1}^{k} m_i!

经典题型：四种迷宫地形

迷宫也有不同地形。第一种是“排列迷宫”：每个房间必须恰好访问一次，顺序不同就算不同路线，比如给三个数字排成所有三位数；第二种是“组合迷宫”：不关心访问顺序，只关心选了哪些房间，比如从十个人里挑三人组队；第三种是“子集迷宫”：每个岔路口都竖着“去/不去”两块牌子，最终得到所有可能的选择；第四种是“棋盘迷宫”：要往迷宫里放置互不攻击的卫兵，每放一个都要检查与已有卫兵是否冲突，比如 N 皇后。

四类题型的回溯代码长得像，但细节差异决定了成败。排列问题用 used 数组标记“某个元素是否已被使用”，因为同一个元素不能重复出现在不同位置；组合与子集问题用 start 索引控制“只能向后选”，天然避免顺序不同造成的重复；棋盘问题则要在递归前完成冲突校验，不满足约束立刻回溯。理解这些差异，比背十道题更有价值。

以组合为例，从 n 个元素里选 k 个，答案的数量由组合数决定：

四种地形本质相通：都是站在岔路口做选择，只是“选择列表的形态”和“终止条件的判定”不同。面试官换着花样出题，你要做的就是用一双火眼金睛辨认出迷宫的地形类型。

C(n,k)=(nk)=n!k! (n−k)!\displaystyle C(n, k) = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}
组合数的分子分母把“顺序不重要”体现得淋漓尽致：先按排列数计数，再除以内部排列带来的多余部分。
  1. 分子 n!n 个元素的全排列总数，这是把“选 k 个”当成“排 k 个位置”的起点。
    n!=n×(n−1)×⋯×1\displaystyle n! = n \times (n-1) \times \cdots \times 1
  2. 分母 k!被选出的 k 个元素内部顺序并不重要，因此要除掉它们自身的全部排列。
    k!=k×(k−1)×⋯×1\displaystyle k! = k \times (k-1) \times \cdots \times 1
  3. 分母 (n-k)!没被选中的 n-k 个元素，内部顺序同样不重要，也要除掉。
    (n−k)!=(n−k)×(n−k−1)×⋯×1\displaystyle (n-k)! = (n-k) \times (n-k-1) \times \cdots \times 1
  4. 组合数整体三者相除得到从 n 个中选 k 个的组合数，也就是组合问题回溯解空间的大小。
    C(n,k)=n!k! (n−k)!\displaystyle C(n,k) = \frac{n!}{k!\,(n-k)!}

复杂度分析：出发前数一数岔路

探险家出发前一定会估算迷宫规模：迷宫太大而干粮有限，就要放弃穷尽式探索；迷宫规模在可承受范围内，才会放心深入。回溯的复杂度分析，本质就是“数清楚状态空间树上有多少个节点，以及每个节点上做了什么操作”。

对于全排列，状态空间树最深处有 n! 个叶子节点，整棵树的节点总数也在 O(N!) 量级；对于组合与子集，节点规模由组合数 C(n,k) 决定。每个节点上，我们还要做路径拷贝、判断终止条件等 O(N) 的额外操作，因此时间开销通常是“节点数 × 单节点操作”。递归的空间开销则要简单得多：递归栈的深度等于路径长度，最多为 n。

数清岔路，探险家才不会把干粮带错。面试中被问到“你这个回溯是 O（多少）”，第一步永远是先数解空间树的节点数，再乘上单节点操作的代价。

T(N)=O(N!⋅N),S(N)=O(N)\displaystyle T(N) = O(N! \cdot N), \qquad S(N) = O(N)
时间开销看“树有多大、每步多贵”，空间开销看“递归栈有多深”，这两行公式就是回溯的完整账本。
  1. 解空间规模 N!全排列的状态空间树约有 N! 个叶子，整棵树的节点总数也在 O(N!) 量级，这是时间的“大头”。
    节点数 =O(N!)\displaystyle \text{节点数 } = O(N!)
  2. 单点额外操作每访问一个节点，记录答案或复制路径都需要 O(N) 的拷贝时间，二者相乘得总时间。
    T(N)=O(N!)⏟节点数×O(N)⏟单点开销\displaystyle T(N) = \underbrace{O(N!)}_{\text{节点数}} \times \underbrace{O(N)}_{\text{单点开销}}
  3. 递归栈深度递归最多同时压入 n 层调用栈，加上一条路径自身的存储，空间开销为 O(N)。
    S(N)=O(N)\displaystyle S(N) = O(N)
  4. 剪枝的影响剪枝跳过注定失败的分支，能大幅缩短实际运行时间，但不改变最坏情形下的渐进复杂度。
    T剪枝后(N)≤O(N!⋅N)\displaystyle T_{\text{剪枝后}}(N) \le O(N! \cdot N)

模板套路：探险手册的标准流程

经验丰富的探险家会把自己的每一步行动整理成一本“探险手册”：走到岔路口→看判定卡决定是否记录→列清单→选一条没走过的路→做记号→深入→退回来时擦掉记号→试试下一条。任何迷宫，照着手册执行都不会乱。回溯的代码模板，就是这份手册的程序化表达。

标准回溯模板的结构高度统一：一个递归函数负责“站在岔路口该做什么”，函数内部先判断终止条件，若不满足则遍历选择列表，对每个候选依次执行“做选择→递归→撤销选择”。模板的骨架人人都背得出来，真正拉开差距的是参数设计与边界处理：入口参数是路径还是下标？选择列表用 used 数组还是 start 索引？空输入要不要提前返回？路径拷贝用浅拷贝还是深拷贝？

手册在手，新迷宫也能从容应对。面试前把这份模板练到肌肉记忆，再把参数设计、边界处理的易错点逐一过一遍，回溯类题目就再也不是拦路虎，而是稳稳的送分题。

backtrack(路径,选择列表)={输出路径,若满足终止条件遍历候选→选择, 递归, 撤销,否则\displaystyle \text{backtrack}(路径, 选择列表) = \begin{cases} \text{输出路径}, & \text{若满足终止条件} \\ \text{遍历候选} \to \text{选择, 递归, 撤销}, & \text{否则} \end{cases}
模板的本质是一棵递归树：是出口就记录，不是出口就遍历候选，每个候选都做“选择—递归—撤销”三连。
  1. 函数签名backtrack 接收当前路径与选择列表两个参数，代表“站在哪个岔路口、还有哪些路可走”。
    backtrack(path,choices)\displaystyle \text{backtrack}(path, choices)
  2. 终止条件分支若路径满足题目要求，例如长度达到 n 或找到合法摆法，就记录答案并返回。
    if condition(path):  record(path);  return\displaystyle \text{if } condition(path): \; \text{record}(path); \; \text{return}
  3. 遍历候选用 for 循环逐个取出选择列表中的候选，相当于逐一看向每个岔路口的走廊。
    for c  in choices:\displaystyle \text{for } c \; \text{in } choices:
  4. 选择与撤销把候选加入路径，递归深入，返回后立刻弹出，完成“走进去→退回来”的完整循环。
    path.append(c);  backtrack(path,choices′);  path.pop()\displaystyle path.\text{append}(c); \; \text{backtrack}(path, choices'); \; path.\text{pop}()
  5. 恢复现场撤销操作保证兄弟分支看到的是未被污染的初始状态，这是回溯与普通递归最大的区别。
    path回到入口前=path进入前\displaystyle path_{\text{回到入口前}} = path_{\text{进入前}}

AI 应用场景

特征组合筛选

阶段：特征工程

解决的问题：训练模型前要从几十个候选特征里挑出最优组合，手工试错效率低且容易漏掉关键组合。回溯枚举所有特征子集，再配合验证集评分做剪枝，能系统化地选出最优特征组合。

具体案例：某推荐系统团队面对 24 个候选特征，用回溯加交叉验证搜索特征子集，每当当前组合的评分已低于历史最优就立即剪枝，把搜索时间从两三天缩短到几小时。

超参数实验矩阵生成

阶段：模型调优

解决的问题：学习率、批大小、网络层数的组合数量爆炸式增长，手动组实验会遗漏关键配置。回溯生成全部参数组合作为实验矩阵，并用早停剪枝跳过明显发散的配置，保证实验覆盖完整。

具体案例：训练 NLP 分类模型时，需要组合 3 个学习率、3 种批大小和 2 种层数，用回溯自动生成 18 组实验并记录结果，快速定位最佳配置，避免人工排列组合的疏漏。

训练资源约束排程

阶段：平台工程

解决的问题：多个训练任务要分配 GPU，且占用时间段不能冲突，本质是 N 皇后式的约束满足问题。回溯枚举所有合法分配方案，再从中选取负载最均衡的一组。

具体案例：AI 平台上每天有 8 个训练任务、4 张 GPU 卡，用回溯快速判断是否存在无冲突的排程方案，并输出全部可行排班供调度系统选择。

Python 演示

python93 行
def permute(nums):    # 全排列: 无重复元素    res, path, n = [], [], len(nums)    used = [False] * n     def dfs():        if len(path) == n:            res.append(path[:])  # 记录答案快照            return        for i in range(n):            if used[i]:                continue            used[i] = True            path.append(nums[i])            dfs()            path.pop()      # 撤销选择, 恢复现场            used[i] = False     dfs()    return res  def permute_unique(nums):    # 含重复元素的全排列: 排序 + 剪枝去重    nums.sort()    res, path, n = [], [], len(nums)    used = [False] * n     def dfs():        if len(path) == n:            res.append(path[:])            return        for i in range(n):            if used[i]:                continue            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:                continue  # 剪枝: 跳过重复分支            used[i] = True            path.append(nums[i])            dfs()            path.pop()            used[i] = False     dfs()    return res  def subsets(nums):    # 子集枚举: 每个元素可选可不选    res, path, n = [], [], len(nums)     def dfs(start):        res.append(path[:])     # 每次进入都记录当前子集        for i in range(start, n):            path.append(nums[i])            dfs(i + 1)            path.pop()     dfs(0)    return res  def solve_n_queens(n):    # N皇后: 返回所有合法摆法    res = []    cols = [-1] * n             # cols[r] = 第 r 行皇后所在的列     def is_ok(r, c):        for r0 in range(r):            c0 = cols[r0]            if c0 == c or abs(c0 - c) == abs(r0 - r):                return False        return True     def dfs(r):        if r == n:            res.append(cols[:])  # 找到一组完整摆法            return        for c in range(n):            if is_ok(r, c):                cols[r] = c      # 做选择                dfs(r + 1)                cols[r] = -1     # 撤销选择, 恢复现场     dfs(0)    return res  if __name__ == "__main__":    print("permute([1,2,3]) =", permute([1, 2, 3]))    print("permute_unique([1,1,2]) =", permute_unique([1, 1, 2]))    print("subsets([1,2,3]) =", subsets([1, 2, 3]))    print("solve_n_queens(4) =", solve_n_queens(4))
目的：本代码实现回溯四件套——全排列、去重排列、子集枚举与 N 皇后求解，覆盖面试中最常见的四类回溯题型。
  1. res.append(path[:])记录答案时必须做拷贝，否则后续 pop 会篡改已保存的结果。
  2. used[i] = True标记该元素已进入当前路径，避免同一元素被重复使用。
  3. path.pop()撤销选择，让路径回到进入递归前的状态，这是回溯的“擦粉笔印”动作。
  4. nums.sort()先排序让相同元素相邻，是去重剪枝的前置条件。
  5. if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:经典去重剪枝：同一层跳过重复元素。
  6. def dfs(start):组合与子集用 start 参数控制只能向后选，天然避免顺序带来的重复。
  7. if r == n:N 皇后的终止条件：所有行都已放置皇后，记录一组完整答案。

常见误区

误区回溯不就是把所有的可能性都暴力试一遍吗？没什么技术含量，只要写个 for 加递归就行了。

正解回溯是“有组织、有计划”的穷举——它按深度优先的次序系统遍历状态空间树，并通过剪枝提前砍掉注定无解的分支，还通过撤销选择保证分支之间互不污染。同样的枚举，会剪枝的人和不会剪枝的人，运行时间可能相差成百上千倍。“穷举”只是底色，“剪枝 + 状态重置”才是回溯的灵魂。

为何常见：回溯的代码结构和双层 for 循环有几分相似，初学者只看到“把所有情况都试了一遍”的表象，忽略了剪枝与撤销这两个关键机制。

误区递归返回后路径变量里的值留着也没关系，反正下一次循环会重新赋值。

正解路径列表是各分支共享的引用，上一个分支留下的元素如果不 pop 掉，会在下一个分支的答案里“阴魂不散”。这就好比探险家画完一条路不擦粉笔印，下一条路会被旧标记误导。撤销选择不是可选项，而是保证每个分支从干净状态出发的必选项。

为何常见：很多人把“局部变量”和“共享引用”搞混，以为 path 每次递归都自动新建了一份，忽略了 Python 中列表是引用传递的事实。

误区在递归里碰到第一个可行解就 return，整棵搜索树不就停下来了？

正解return 只结束当前这层递归函数的执行，控制权会回到上一层调用处，继续执行循环里下一个候选。想只找一个解，需要额外用全局标志位或异常机制“引爆”整棵搜索树；想找全部解，则要记录答案后继续遍历。把“结束一层”和“结束整个搜索”混为一谈，是回溯面试现场最常见的翻车点。

为何常见：因为很多题目（例如二叉树的路径和）用 return 就能返回最终结果，大家把“函数返回”误当成了“搜索终止”。

误区回溯和动态规划都用了递归，还都能加缓存加速，它们应该是同一种方法。

正解回溯解决的是“枚举所有可行解”的搜索问题，解空间树可能是指数级大，且各分支路径不同、互相独立，很难用缓存合并；动态规划解决的是“子问题重叠”的最优化问题，用 dp 表或记忆化把重复子问题的结果存起来复用。看到“求所有方案”用回溯，看到“求最优值且有重叠子问题”用动态规划。

为何常见：两者都基于递归展开，动态规划里也有“状态”和“转移”的说法，表面上很像，初学者容易张冠李戴。

面试题

Q1. 回溯算法在解空间树上的搜索顺序是什么？

单选题 · easy

  • A.广度优先逐层扫描
  • B.深度优先一路到底← 正确答案
  • C.随机跳跃试探搜索
  • D.贪心选择局部最优

答案：B。回溯从根节点出发，沿一条分支不断深入，直到无法继续才退回父节点换路，这正是深度优先遍历的定义。广度优先需要借助队列逐层展开，与“原路退回”的机制不符；随机搜索与贪心算法都不保证系统覆盖全部解，故排除。

Q2. 回溯算法三大要素中，“判断当前路径是否构成完整答案”对应的是？

单选题 · easy

  • A.记录路径的列表
  • B.判断出口的条件← 正确答案
  • C.可选分支的集合
  • D.撤销操作的步骤

答案：B。迷宫探险三件套中，“判断出口的条件”对应算法里的终止条件——当路径长度等于目标值（或满足题目约束）时，记录答案并返回。选择列表决定“还能走哪条路”，路径记录“已经怎么走的”，撤销操作负责“退回来时恢复原样”，都不是判停的工具。

Q3. 在递归前后分别执行“加入候选”与“弹出候选”，这种操作组合叫作？

单选题 · mid

  • A.选择与撤销选择← 正确答案
  • B.排序与快速分区
  • C.压缩与解压编码
  • D.装载与卸载栈帧

答案：A。回溯的每次递归都遵循“选择—递归—撤销”三步曲：先把候选加入路径，递归深入，返回后再弹出。这一进一出保证共享的路径变量在每个分支开始时都保持相同状态。排序分区、压缩编码、栈帧装载与回溯流程无关。

Q4. 求含重复元素数组的全排列时，常用的去重剪枝手段是？

单选题 · mid

  • A.排序后跳过相邻重复← 正确答案
  • B.用哈希表记录排列去重
  • C.递归前随机打乱数组
  • D.每次取最小值当头部

答案：A。先将数组排序让相同元素紧邻，再在循环里跳过“与前一个元素相同且前一个元素未被使用”的分支，即可系统去重。用哈希表存储全部排列虽然也能去重，但会先产生大量重复结果，时间与空间开销远高于剪枝；打乱数组与取最小值当头部都会破坏搜索的系统性。

Q5. N 皇后用列集合与对角线集合查重后，判断单次落子合法性的开销为？

单选题 · mid

  • A.O(1) 常数时间查询← 正确答案
  • B.O(N) 逐列扫描棋盘
  • C.O(N²) 遍历全部格子
  • D.O(N!) 枚举全部摆法

答案：A。用三个布尔数组分别记录“列、主对角线、副对角线”的占用情况后，判断某位置能否放皇后只需查询三个标记，单次开销是 O(1)。逐列扫描棋盘是朴素实现，复杂度为 O(N)；遍历全部格子与枚举全部摆法更是没有必要。

Q6. 回溯算法适合解决下列哪些问题类型？

多选题 · mid

  • A.枚举全部排列和组合← 正确答案
  • B.求解全部可行棋盘摆法← 正确答案
  • C.求两点间的最短路径
  • D.满足约束的组合搜索← 正确答案

答案：ABD。回溯擅长“枚举 + 约束过滤”：排列、组合、子集、N 皇后、数独都属于此类，A、B、D 都是典型场景。求两点间最短路径是图论问题，有 Dijkstra、Floyd 等专用算法，用回溯会指数爆炸且得不到最优保证，故不选 C。

Q7. 关于回溯中“撤销选择”操作，下列说法正确的有？

多选题 · mid

  • A.恢复路径变量的现场状态← 正确答案
  • B.避免答案被旧选择污染← 正确答案
  • C.可以直接降低时间复杂度
  • D.等价于终止条件的判断

答案：AB。路径列表是各分支共享的，若不撤销，上一个分支的选择会残留在 path 里，污染兄弟分支的答案。撤销选择的作用是恢复现场与避免答案被污染，A、B 正确。真正降低时间复杂度的操作是剪枝而非撤销；终止条件负责判断是否记录答案，与撤销无关，C、D 错误。

Q8. 子集问题在每层递归开头记录当前路径，最终收集到的是？

单选题 · easy

  • A.全部子集的完整集合← 正确答案
  • B.元素个数最多的子集
  • C.字典序最小的排列
  • D.只含单个元素的子集

答案：A。子集问题的经典写法是在每层递归开头记录当前路径快照。路径经历了“空→加 1→加 1 加 2→加 1 加 3”等过程，每次快照恰好对应一个不同子集，最终收集到全部子集。若只记录叶子路径，会漏掉所有“不用尽元素”的子集，B、C、D 都不是自然结果。

Q9. 全排列回溯的递归调用栈深度，与下列哪一项直接相关？

单选题 · mid

  • A.待排列元素的总数← 正确答案
  • B.排列方案的总个数
  • C.数组中重复元素数
  • D.输入数据的内存大小

答案：A。递归调用栈的深度等于“当前路径的长度”。全排列中路径每层增加一个元素，最多填满 n 个元素，因此栈深为 O(N)。方案总数 N! 是树的大小而非栈深；重复元素数与输入数据的内存大小都不决定递归深度。

Q10. 关于回溯算法的剪枝优化，下列表述正确的有？

多选题 · hard

  • A.利用约束条件提前终止分支← 正确答案
  • B.跳过永远不会产生可行解的分支← 正确答案
  • C.剪枝会漏掉所有正确答案
  • D.剪枝不改变最坏时间复杂度← 正确答案

答案：ABD。剪枝利用题目约束提前判断分支注定无解并跳过，A、B 正确。剪枝剔除的是“不可能产生可行解”的分支，不会漏掉正确答案，C 错误。最坏情形（如约束很弱）下搜索仍可能遍历整棵树，因此渐进复杂度不变，D 正确。