一文搞懂回溯法框架：排列、组合、子集的去重与剪枝策略全解析

排列、组合、子集是回溯法的入门三件套，也是「一看就会，一写就废」的重灾区。看题解时人人都能点头，自己落笔时却总是纠结：这里该不该传 start？收集答案写在哪一行？有重复元素时剪枝条件为什么是那个看起来毫无道理的判断？

问题不在题，在于没有建立统一视角。这三类题（以及它们的大量变体）共享同一套决策树框架，差异只是框架里两三个变量的取法。这篇文章先把框架立起来，再逐个拆解三类问题的差异，最后给出含重复元素场景的去重与剪枝策略。读完你会发现，回溯题的变体再多，骨架从来没变过。

问题背景：回溯的本质是带剪枝的决策树遍历

回溯法解决的是「枚举所有可能并筛选合法解」的问题。它的本质是对一棵隐式决策树做系统化遍历：树的每个节点代表「决策进行到一半的状态」，每条边代表「做一个选择」，叶子代表「一条完整路径」。所谓回溯，就是在从叶子往回走时撤销刚才的选择，让现场恢复干净，好尝试兄弟分支。

很多教程把它说得神乎其神，其实回溯就是结构化管理过的暴力枚举加上提前止损。它不降低理论复杂度的量级——子集类问题本质就是 2^n 种状态，排列类就是 n! 种——它的价值在于：用统一的框架保证不重不漏，用剪枝把大量「注定无解」的分支提前砍掉，让实际的搜索空间远小于名义上的解空间。

这也决定了适用边界：回溯适用于解空间可以枚举、但能用剪枝大幅收缩的场景，典型规模是 n 在 20 到 30 以内（2^20 约百万，2^30 约十亿，量级差就在这里）。n 再大就得换思路——动态规划、贪心或数学构造。拿到题先估解空间规模，是做回溯题的第一反应。

思路推导：一套框架，三类问题的差异

框架由三要素构成：路径（已经做出的选择，通常用列表 path 维护）、选择列表（当前层还能做的选择）、结束条件（何时把 path 收进答案）。三类问题在这个框架里的差异，恰好对应三个正交的维度：

差异一：收集时机。 子集问题的每个节点都是一个合法答案——路过就收集，不需要任何条件；组合问题只收集「长度恰好为 k」的节点；排列问题只收集「长度等于 n」的节点。一行代码的位置差异，就是题型的分水岭。

差异二：选择列表的收缩方式。 组合和子集用 start 参数：第 i 层只能从第 i 个元素往后选，保证「组合内元素递增」，从而天然避免 [1,2] 和 [2,1] 被当成两个答案。排列则相反：每层都可以从全集中选，但要用 used 数组排除已在路径里的元素——排列关心顺序，[1,2] 和 [2,1] 是两个不同的答案。

用文字画一棵树就能看清：求 [1,2,3] 的组合，根节点下第一层可以选 1、2、3；选了 1 之后第二层只能选 2、3（start 往后推），选了 2 之后第三层只能选 3。树沿着「只能向右走」的方向生长，同一组合只会在一条路径上被拼出来。而排列的树每一层都是全集中挖去已用元素，同样的三个元素以不同顺序长在不同的枝上。

差异三：结束时的动作。 三者相同：到达收集点时必须写入 path 的浅拷贝而不是 path 本身——path 是全程复用的工作区，等遍历结束它会被清空，直接存引用最后得到一堆空列表，这是回溯题出错率第一高的地方。

剪枝与去重：把指数级砍到可接受

去重的原理：树层去重。 输入含重复元素（如 [1,2,2]）时，同一层如果既有分支 A 选了第一个 2、又有分支 B 选了第二个 2，两棵子树长出来完全一样——去重要砍的是这种横向的兄弟分支重复，而要保留纵向的路径内重复（[2,2] 作为子集是合法的）。写法是：先排序让相同元素相邻，遍历时若 nums[i] == nums[i-1] 且前一个相同元素「本层没用过」（not used[i-1]），跳过 i。这个条件初看费解，画树一看就懂：used[i-1] 为 True 说明我们正在 i-1 的子树里纵向深入（合法）；为 False 说明 i-1 的分支刚被回溯过、以这个值开头的兄弟子树已经搜完了（重复，砍）。

可行性剪枝。 组合求和类问题里，当前路径和已超 target 时直接 return，连循环都不进——整棵子树被一刀砍掉。

上下界剪枝。 求长度为 k 的组合时，若剩余候选元素不足以凑满 k 个，后面的循环不必再进。把它写成循环边界的收缩形式：range(start, n + 1 - (k - len(path)) + 1)，每一层都少做无用功，对深树的收益是乘法级的。排序之后还能做更狠的极值剪枝：如果当前值加上后续最小可能值都已超界，整段 break 掉。

实操代码：四个可运行模板

三兄弟的基础模板（语言：Python）：

def subsets(nums: list[int]) -> list[list[int]]:
    """子集：路过就收集，start 防止回头重复"""
    res: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        res.append(path[:])            # 浅拷贝收集：子集问题的标志
        for i in range(start, len(nums)):
            path.append(nums[i])       # 做选择
            backtrack(i + 1)           # 下一层从 i+1 起，元素不复用
            path.pop()                 # 撤销选择，现场恢复

    backtrack(0)
    return res


def combine(n: int, k: int) -> list[list[int]]:
    """组合 [1..n] 中所有 k 元组合：子集 + 长度条件 + 上下界剪枝"""
    res: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        if len(path) == k:             # 达标才收集
            res.append(path[:])
            return
        # 剪枝：剩余候选不够凑满 k 个时，循环直接不到那里
        for i in range(start, n + 1 - (k - len(path)) + 1):
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return res


def permute(nums: list[int]) -> list[list[int]]:
    """排列：每层从全集选，used 排除已在路径中的元素"""
    res: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):     # 满长才收集
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue               # 已在路径里，跳过
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False            # 与 append/True 严格成对出现

    backtrack()
    return res

含重复元素的全排列去重模板：

def permute_unique(nums: list[int]) -> list[list[int]]:
    """含重复元素的全排列：排序 + 树层去重"""
    nums.sort()                        # 去重前提：相同元素必须相邻
    res: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):
            res.append(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])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return res

复杂度分析：子集共 2^n 个答案，每个复制 O(n)，总 O(2^n·n)；组合量级为 C(n,k)·k；排列为 n! 个答案、每个复制 O(n)，总 O(n·n!)。这些是「输出规模本身」决定的下界，剪枝改变的是常数与被砍掉的比例，改变不了量级——这也是为什么回溯题要先看 n 的范围。空间上递归栈与 used 数组为 O(n)，结果空间另计。

避坑总结

1. 收集时忘写 path[:] 是第一大错。存引用最后全空，存浅拷贝才安全；元素是可变对象时还要考虑深拷贝。
2. 收集时机按题型对号入座：子集路过就收、组合达标才收、排列满长才收。写在 if 外面还是里面，差一个条件就是不同题型。
3. 组合/子集里 backtrack(i+1) 写成 backtrack(i) 会让元素无限复用，结果错误甚至爆栈；排列里则要保证 used 的 True/False 与 append/pop 严格成对，漏一对现场就脏了。
4. 去重前必须先排序。树层去重依赖「相同元素相邻」这一前提，忘了排序等于没去重，复杂度白白乘上去。
5. 别用 set 暴力去重。把结果序列化进集合去重虽然能过小数据，但付出了哈希化的额外代价，还掩盖了「重复从哪来」的结构理解；排序加剪枝的判定是 O(1) 的，这才是面试想看到的写法。

写在最后

回溯法的所有「难」，其实都难在决策树长什么样：选择列表怎么收缩、收集点放在哪、哪些分支重复、哪些分支必死。把这三个问题用框架变量表达清楚，排列组合子集及其变体就都成了同一道题的换皮。先画树、再写码、最后上剪枝——这个顺序坚持几道题，「一看就会一写就废」的阶段就过去了。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。