算法►回溯

子集型回溯方法论得应用（2026-01-08）

一、输入角度的子集型回溯

子集型回溯是一类通过枚举每个元素“选 or 不选”来构造答案集合的回溯问题。
其核心思想是：

对输入集合中的每一个元素，都做一次“是否加入当前解”的选择，通过递归枚举所有可能的子集。

由于每个元素只有两种状态（选 / 不选），因此这类问题天然覆盖所有可能情况，不会重、不漏。

二、子集型回溯的统一模板

子集型回溯的 DFS 过程通常包含三个核心要素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(i, 输入集合，当前状态):
	// n 为输入集合长度
    if i == n:
		// 说明当前轮枚举完了输入集合
        更新答案
        return

    // 不选第 i 个元素
    dfs(i + 1, 输入集合，当前状态)

    // 选第 i 个元素（有条件）
    if check(i, 当前状态):
        选择 i
        dfs(i + 1, 输入集合，新状态)
        撤销选择

其中：

  • i：当前处理到第 i 个元素
  • 当前状态：路径（已选元素 / 剩余资源 / 当前得分等）
  • check：是否允许“选”的条件判断（条件回溯的关键）

三、扩展题目统一拆解

下面 6 道题，本质上都可以统一为「子集型回溯 + 条件判断」。

LCP51. 烹饪料理

建模方式：

  • 枚举第 i 道料理：做 or 不做
  • 选的条件：材料足够

状态维护：

  • 剩余材料数组

典型的「资源约束型子集回溯」

2397. 被列覆盖的最多行数

建模方式：

  • 枚举第 i 列：选 or 不选
  • 选的条件：已选列数 ≤ numSelect

关键剪枝：

  • 如果 剩余列数 ≤ 剩余可选数 → 必须全选

子集型回溯 + 强剪枝

1239. 串联字符串的最大长度

建模方式：

  • 枚举每个字符串：选 or 不选

选的条件：

  1. 字符串内部不能有重复字符
  2. 与当前已选字符串字符集不能冲突

状态设计：

  • 使用 boolean[26] 维护字符占用情况

典型的「集合冲突约束型回溯」

2212. 射箭比赛中的最大得分

建模方式：

  • 枚举每个得分区间是否争夺

选的条件：

  • 剩余箭数 ≥ alice[i] + 1

状态维护：

  • 剩余箭数
  • 当前得分

本质是 资源分配 + 子集枚举

2698. 求一个整数的惩罚数

建模方式：

  • 对 i² 的字符串进行切割
  • 每一刀：切 or 不切

选的条件：

  • 当前分割出的数字之和 ≤ i

本质是 字符串分割型子集回溯

93. 复原 IP 地址（从答案角度分析）

建模方式：

  • 字符串分割，一共分割为 4 段
  • 枚举第 i 段从哪里分割

隐含条件（关键）：

  1. 必须切成 4 段
  2. 每段 ∈ [0,255]
  3. 不能有前导 0

带分割约束的字符串回溯

五、子集型回溯的优化与剪枝

条件剪枝（最常见）

  • 选之前判断是否合法
  • 不合法直接跳过

提前终止（上界剪枝）

  • 剩余元素即使全选，也不可能更优
  • 直接 return

强制选择

  • 剩余元素数 ≤ 剩余配额
  • 不再分支，直接全选

六、心得体会与方法论总结

  • 子集型回溯本质是一种暴力但系统的枚举方法
  • 通过“选 / 不选”两条分支，可以完整覆盖解空间
  • 时间复杂度通常为 O(2^n)，但剪枝决定了实际性能
  • 带条件的子集回溯，核心是：
    • 把“是否能选”的逻辑抽离成 check
    • 让 DFS 结构保持干净、统一
  • 很多看似不同的题（资源分配、字符串切割、组合选择），在建模层面是同一类问题

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。