组合型回溯 + 剪枝
一句话总结：
组合型回溯本质仍是子集型回溯，但通过“组合约束 + 单调性剪枝”，将指数级搜索空间大幅收缩，只遍历“有可能成为答案”的分支。
一、什么是组合型回溯？
在回溯问题中，我们通常会遇到两类经典模型：
- 子集型回溯：
枚举所有可能的子集（选 / 不选），不关心长度或数值约束 - 组合型回溯：
在子集枚举的基础上，只保留满足条件的组合
常见的组合约束包括：
- 固定长度（如选 k 个数）
- 固定和（如和为 target）
- 结构合法性（如括号匹配、IP 段合法）
因此，组合型回溯 = 子集型回溯 + 条件约束 + 剪枝。
二、组合型回溯的核心思想
组合型回溯的关键并不在「怎么枚举」，而在于：
当前状态已经不可能构成合法解时，要尽早停止搜索
这正是剪枝的价值所在。
常见剪枝维度
- 数量剪枝
- 剩余可选元素 < 还需要选的数量 → 直接返回
- 数值剪枝（选择元素为正）
- 当前和已经超过 target
- 即使选最大值，也无法达到 target
- 结构剪枝
- 不满足合法结构（如右括号多于左括号）
这些剪枝往往都依赖于一个核心性质：
单调性：
当前状态不满足条件，向下扩展只会更不满足。
三、典型题目拆解与剪枝思路
77. 组合（Combinations）
目标：从 [1…n] 中选 k 个数
关键剪枝
- 数量剪枝
- 剩余数字个数 < 还需要选择的数量 → 直接返回
- 提前返回
- 当已选数量 == k，记录答案，不再向下搜索
本质理解
这是一个固定长度的组合问题，搜索树深度是确定的，剪枝点非常清晰。
216. 组合总和 III
目标：从 [1…9] 中选 k 个数，和为 n
关键剪枝
leftTarget < 0- 所有数均为正数，后续必然无解
leftTarget > 剩余可选数字的最大可能和- 即使全选最大值，也无法凑够
- 剩余数字个数 < 还需要选择的数量
关键
- 同时利用了「一大一小」两种剪枝方向
- 体现出数值约束与数量约束的对称性
22. 括号生成
目标：生成 n 对合法括号
状态定义
left：已使用左括号数量right：已使用右括号数量
剪枝规则
left > n→ 非法right > left→ 非法
本质理解
这道题可以视为一种带结构约束的组合回溯：
- “选” → 加左括号
- “不选” → 加右括号（但有条件）
本质不是排列，而是合法结构的组合生成。
39. 组合总和（可重复选择）
目标：元素可重复选，和为 target
关键剪枝
leftTarget < 0→ 直接返回leftTarget == 0→ 记录答案并返回排序 + 剪枝
若当前元素 >
leftTarget，后续元素更大，可直接 break
可重复选择的表达
- 使用
dfs(i)表示当前元素可再次选择 - 通过起始索引控制是否允许重复
93. 复原 IP 地址
目标：将字符串分割为 4 段合法 IP
强剪枝条件
字符数量剪枝
剩余字符数 ∉
[剩余段数, 剩余段数 * 3]数值剪枝
当前段 > 255
前导零剪枝
段以
0开头但长度 > 1
补充思路
- 由于段数固定为 4
- 该题也可以用 三重循环 实现
- 但回溯解法在结构上更统一、可复用性更强
四、方法论总结：如何写好组合型回溯？
推荐解题步骤
先不剪枝，写出正确解
明确以下要素：
状态变量（路径、索引、剩余目标）
终止条件
回看搜索树，问自己：
当前状态已经不可能成功了吗？
将「不可能成功」的情况提前 return
一个重要认知
剪枝为了利用题目的单调性。
- 当前不满足 → 未来一定不满足
- 才是可以安全剪枝的前提
五、个人心得体会
组合型回溯并不是新的模型
它只是对子集型回溯的“条件收敛”实战中：
先保证正确性、再逐步加剪枝，思路更清晰
多数高质量剪枝，都来源于：
- 数量边界
- 数值上下界
- 结构合法性
当你能一眼看出「当前状态是否还有希望」，回溯题就不再是暴力搜索，而是受控的状态枚举。
相关代码
本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。