6.2 现场十七：回溯与剪枝解全排列

6.2 现场十七：回溯与剪枝解全排列

本节摘要：终面的第二题：回溯法求全排列，重复元素的去重剪枝是真正的考点。本题看似模板，实则处处是追问素材：状态怎么恢复、剪枝条件为什么长那样、复杂度这笔账怎么一笔一笔算、与动态规划的分界在哪里。它承接现场十六的状态设计，也呼应第 1 章迭代器现场的惰性思想。

别把全排列当成背模板的题——它的考点是搜索树。同样这段代码，能画出递归树、说清每个剪枝分支砍掉了哪棵子树的人，与只会默写的人，在终面面试官眼里属于不同物种。这道题也恰好补上现场十六留下的对照面：动态规划吃重叠子问题，回溯吃互斥选择，各自的食材互不串味。

题面与考点

"写一个函数输出全部排列。先给无重复元素的版本；然后输入里有重复数字，要求输出不能有重复排列，说明你的剪枝条件。最后算清楚复杂度：时间、空间，剪枝到底省了什么。"

考点藏在追问的顺序里：基础版筛动手能力，去重版筛思维精度，复杂度版筛诚实度——多数人答得出阶乘，答不出阶乘之外那笔路径拷贝的账。

现场推演

候选人先画递归树再写代码：根节点是空路径，每个节点分叉出"还没被用过"的元素，叶子就是完整排列。回溯的三件套他直接报出来：路径（已经做了的选择）、选择列表（还能选的元素）、结束条件（路径长度等于输入长度）。写完基础版，他主动先跑重复元素的用例来暴露问题：

def perm_dup(nums):
    nums = sorted(nums)                      # 去重的前提：相同元素相邻
    res, path, used = [], [], [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            res.append(path.copy())          # 必须拷贝，path 是共享的草稿
            return
        for i in range(len(nums)):
            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

print(perm_dup([1, 1, 2]))
​

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
​

输出恰好是三种合法排列，没有重复。候选人没有停笔，把去重前后的叶子数对比了一下：不去重时三个元素本该有六片叶子，重复的一被砍掉一半——剪枝砍的不是常数，是整棵子树。随后他又补了交换法版本作对照：

def perm_swap(nums):
    res = []

    def dfs(k):
        if k == len(nums):
            res.append(nums.copy())
            return
        for i in range(k, len(nums)):
            nums[k], nums[i] = nums[i], nums[k]   # 把候选换到位置 k
            dfs(k + 1)
            nums[k], nums[i] = nums[i], nums[k]   # 换回来，恢复现场

    dfs(0)
    return res

print('交换法在无重复输入下的排列数:', len(perm_swap([1, 2, 3])))
print('交换法遇到重复输入:', len(perm_swap([1, 1, 2])))
​

交换法在无重复输入下的排列数: 6
交换法遇到重复输入: 6
​

对照的结论很有意思：交换法代码更短、不用 used 数组，但遇到重复元素会输出重复排列——它天然不带同层去重的钩子，硬要塞进去得先排序再在循环里跳过同值候选，可读性反而更差。候选人的取舍："面试手写首选 used 版，剪枝条件一目了然；交换法留作'有没有更省空间的写法'的追加答案。"

追问链

追问一：剪枝条件 not used[i-1] 每个字什么意思？ 候选人逐字拆解："nums[i] == nums[i-1] 保证谈的是一对相同元素；排序保证它们相邻；关键在 not used[i-1]——前一个相同元素还没被用过，说明当前正处在'同一层'的尝试里，上一个同值元素的分支已经探索完回退了，再选当前这个必然产出重复排列，砍掉。如果条件反过来写成 used[i-1]，保留的是另一批等价分支，结果同样不重复，但搜索树的形状不同、走位不同——所以面试官真正想听的是：你能证明你写的那个条件与'同层去重'等价。"

追问二：复杂度的账怎么算？ "叶子有 n 的阶乘片，从根到每片叶子路径长 n，拷贝路径要 O(n)，时间就是 O(n 乘 n 的阶乘)。空间是递归深度 O(n) 加 used 数组 O(n)，输出不算在内的话就是这样。剪枝省的是重复排列对应的整棵子树——重复元素越多省得越狠，极端情况全部元素相同，从阶乘砍到一。"

追问三：这个题什么时候该换动态规划？ "看子问题重不重叠。排列的每个前缀路径互不相同，没有重叠子问题，记忆化无账可记——这正是回溯的主场；换成'最长递增子序列'那种前缀高度重叠的题，动态规划立刻反超。判断动作只有一个：画出的搜索树里，同一个节点被到达几次。"

优化与变式

最值得写的变式是把回溯改成生成器：把 res.append 换成 yield path.copy()，调用方就能逐个消费排列，不必等全量生成——n 一大，全量排列本身就是天文数字，惰性求值从优雅变成刚需。这与第 1 章迭代器现场的精神完全同源：遍历协议与产生过程解耦。其他变式都在换剪枝条件：子集树不加任何剪枝、组合树加"起点递增"、N 皇后加对角线冲突检查、数独加可行性即时否决——回溯的骨架一个字不用改，变的只是"什么分支该死"。面试官若追问"海量数据下怎么数排列"，诚实答案是：精确计数会溢出也会爆炸，转 modular 运算或近似估计，别硬扛。

失误复盘

高频翻车点：忘了排序，去重条件静默失效——排序是去重的隐形前提，漏了它代码照样跑、结果照样错；path.pop 或 used 恢复漏写一行，排列缺枝少叶；res.append(path) 不拷贝，最后得到一列空列表——所有元素指向同一个被清空的草稿；交换法忘了换回来，输入数组被搅乱；复杂度只报阶乘，被追问"拷贝不算钱吗"当场卡壳。还有一种终面特有的表达失误：画递归树时只画两层就急着写代码，被要求"把你砍掉的子树画出来"时画不出——剪枝题的证据链在树上，不在代码里。

主线候选人这一场的高光是主动跑 [1, 1, 2] 用例：他没等面试官出重复版，自己先把 bug 暴露在自己的屏幕上。面试官评语："把面试官还没问的坑自己先踩一遍，这是终面最省时间的生活方式。"

关键直觉：回溯的代码只有"选择、递进、恢复"三个动作，真正的智力密度全在剪枝条件与递归树里——手是抄的，树是想的。