题目
有效 IP 地址由
四个 0-255 的整数组成，中间用
'.' 分隔，且每个整数
不能有前导零（
"0" 合法，
"01" 非法）。
给定只含数字的字符串
s，返回
所有可能的有效 IP 地址，顺序不限。
输入: s = "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
输入: s = "0000"
输出: ["0.0.0.0"]
输入: s = "010010"
输出: ["0.10.0.10", "0.100.1.0"] （"01"、"010" 都因前导零非法）
一、核心洞察：回溯就是递归写的组合枚举
先看清这题（LC 93）的规模：把
s 切成 4 段 = 在
n - 1 个缝隙里
选 3 个切点。每段 1-3 位，所以
s 长度必须在
[4, 12]，切点组合数最多
C(11, 3) = 165 ——
搜索空间天生有界，是个常数。
所以"回溯"在这里不是性能焦虑，而是组织方式。真正值得设计的是
剪枝分两层，它们回答两个不同的问题：
可行性剪枝是本题效率的关键，也是最容易漏的：没有它答案照样对（走到底自然失败），但会白搜很多层。第一段切
"2" 这个例子最能说明两层剪枝的区别 ——
"2" 是个完全合法的段，错的是"往后看"的可行性。
二、拆解：剪枝分两层
2.1 递归结构
每层切一段：尝试 1 / 2 / 3 位 → 检查 → 合法就带着新段深入，切满 4 段且
恰好用完全部数字收答案。
def restoreIpAddresses(s: str) -> list[str]:
ans = []
n = len(s)
def dfs(pos: int, path: list[str]) -> None:
if len(path) == 4:
if pos == n: # 恰好用完
ans.append('.'.join(path))
return
remain_segs = 4 - len(path)
for seg_len in (1, 2, 3):
if pos + seg_len > n: # 末尾不够切
continue
seg = s[pos:pos + seg_len]
if seg[0] == '0' and seg_len > 1: # 层一：前导零
continue
if int(seg) > 255: # 层一：超出范围
continue
rest = n - pos - seg_len # 层二：可行性
segs = remain_segs - 1
if segs > 0 and not (segs <= rest <= segs * 3):
continue
dfs(pos + seg_len, path + [seg]) # 深入（path + [...] 免手动回溯）
if 4 <= n <= 12:
dfs(0, [])
return ans
2.2 三个细节
- 第 4 段必须恰好用完：切完第 4 段还剩数字（或没切到头）都直接判死 —— 4 段要"不多不少"地覆盖整串；
"0" 合法、"0x" 非法：判断条件是 seg[0] == '0' and seg_len > 1，不是"以 0 开头全剪"；path + [seg] 免手动回溯：每次传新列表，天然不用 pop()（代价是多复制，规模小无所谓，见坑 4 的另一种写法）。
三、动画怎么看
动画是一行字符格子 + 分隔标记：
- 已切好的段之间画橙色实竖线（分隔点就是你插的
'.'）；
- try 帧：当前尝试的段区间 —— 合法（ok）淡金 + 深入；被剪则灰虚格，横幅给出剪枝原因（
前导零 / 511 > 255 / 长度不可行），暂定分隔画灰虚线；
- answer 帧：第 4 段恰好用完全部数字，answers 区亮出新答案；
- 回溯是隐式的：一条分支试完 1/2/3 位后，竖线退回去，换上一层的下一条分支。
主例
"25525511135" 一共 21 次尝试收 2 个答案 —— 注意开场第一刀
try "2"：段完全合法，却被
可行性剪掉（剩 10 位 > 3 段 × 3 位），这就是两层剪枝里的第二层。
四、完整推演表
以
"25525511135" 为主例（11 位，切第 1 段起）：
对照前导零例子
"010010"：第一段只能切
"0"（合法单零），后面
"01"、
"010" 全被前导零剪 —— 最终只有
["0.10.0.10", "0.100.1.0"]。
五、变体：三重循环枚举与同族题
5.1 不写回溯：三重循环枚举切点
既然只是"选 3 个切点"，三重循环也能写：
def restoreIpAddresses(s: str) -> list[str]:
n, res = len(s), []
if not (4 <= n <= 12):
return res
for i in range(1, 4):
for j in range(i + 1, i + 4):
for k in range(j + 1, j + 4):
if k >= n:
continue
parts = (s[:i], s[i:j], s[j:k], s[k:])
if all(valid(seg) for seg in parts):
res.append('.'.join(parts))
return res
—— 递归层数固定（4）、每层分支固定（3）时，展开成循环完全等价。什么时候值得写递归回溯？
约束条件是"动态的"时：段数不定、剪枝依赖前面路径的状态（如
segs 与剩余长度的联动）时，递归结构更清晰。这题两者皆可，面试写回溯（通用模板，追问变体时好扩展）。
5.2 同族题
家族口诀：
"每层做一个选择 + 检查合法性 + 递归 + 回溯"是回溯模板的四件套；合法性检查永远分两层 —— 这个选择本身行不行（段），以及这条路往后还有没有戏（可行性）。
六、Java 版
public List<String> restoreIpAddresses(String s) {
List<String> ans = new ArrayList<>();
int n = s.length();
if (n < 4 || n > 12) return ans;
dfs(s, 0, new ArrayList<>(), ans);
return ans;
}
private void dfs(String s, int pos, List<String> path, List<String> ans) {
if (path.size() == 4) {
if (pos == s.length()) ans.add(String.join(".", path));
return;
}
int remainSegs = 4 - path.size();
for (int len = 1; len <= 3; len++) {
if (pos + len > s.length()) continue;
String seg = s.substring(pos, pos + len);
if (seg.charAt(0) == '0' && len > 1) continue; // 前导零
if (Integer.parseInt(seg) > 255) continue; // 超出范围
int rest = s.length() - pos - len;
int segs = remainSegs - 1;
if (segs > 0 && (rest < segs || rest > segs * 3)) continue; // 可行性
path.add(seg); // 手动回溯版
dfs(s, pos + len, path, ans);
path.remove(path.size() - 1);
}
}
Java 版注意
Integer.parseInt(seg) 安全 ——
seg 最多 3 位；
path 是共享列表，
必须手动 remove 回溯（Python 例子里
path + [seg] 传新列表的写法在 Java 里对应每次 new，代价更大，惯用 add/remove）。
七、边界情况
八、复杂度
- 时间 O(C(n-1, 3) × n) = O(1)：切点组合最多 165 个，每个验证拼串 O(n)，
n ≤ 12 —— 整题是常数级的（输入本身有界）。
- 空间 O(4)：递归深度固定 4 层，path 最多 4 段；答案列表不算额外空间。
这也是本题和"一般回溯题"的本质区别：一般回溯的复杂度是指数，这题因为 IP 格式天生有界，
剪枝的作用是"少走几十条路"，而不是"把指数降下来"。
九、常见坑
9.1 前导零一刀切
把"以 0 开头"全剪了，连
"0" 一起杀 ——
"0000" →
["0.0.0.0"] 会空手而归。正确条件：
seg[0] == '0' and len > 1。单段
"0" 是完全合法的整数。
9.2 第 4 段不要求"恰好用完"
切满 4 段就 join 收答案 —— 但第 4 段后面的数字被无声丢掉，
"25525511135" 会多出
"255.255.11.13" 这种假答案（剩个
"5" 没进任何段）。第 4 段就是
剩余的全部数字：要么恰好构成合法段收答案，要么整条路作废。
9.3 用 int() 转换前不防"空段"
int('') 直接抛异常。切点循环边界写错（如
k <= n 而不是
k < n）会产生空段。防御次序：先判长度够不够切，再取段、再验值。
9.4 共享 path 忘了回溯（或复制过度）
Java/C++ 里
path 传引用，深入前
add、返回后必须
remove；漏了 remove 会让已收答案被后续分支污染。Python 用
path + [seg] 传新列表可免 pop，但要明白这是"复制换安全"。
9.5 漏掉可行性剪枝（不算 bug，但丢分）
没有可行性检查答案也对，只是白搜 —— 面试官会追问"还能怎么优化"，可行性剪枝（剩余位数 ∈ [segs, segs × 3]）就是标准答案之一。它在
段合法但整条路走不通时发挥作用（如第一段
"2"），这是段级检查覆盖不到的。
9.6 忘了长度域 [4, 12] 的提前拒绝
长度 13、长度 3 的输入直接返回空，不必进搜索。写在入口处一行，既是效率也是表达："这个输入在结构上就不可能"。
十、面试怎么答
- 一句话定性："选 3 个切点，每段 1-3 位 —— 搜索空间 C(n-1, 3) ≤ 165，回溯模板四件套。"
- 先报剪枝分层："段合法性（前导零、>255）+ 可行性（剩余位数 ∈ [segs, segs × 3]）—— 第二层常被漏，它管的是'段合法但整条路走不通'。"
- 主动提两个特判："第 4 段必须恰好用完全部数字；
"0" 合法、"0x" 非法。"
- 对照枚举循环："层数和分支都固定，三重循环展开等价；回溯胜在模板通用。"
- 复杂度：常数级（输入 ≤ 12 位），递归深度 4。
- 追问准备：LC 131（段合法性换成"是回文"）、LC 22（可行性剪枝的经典）—— 都是同一个模板换检查条件。
结语
复原 IP 地址是回溯入门的标准样本：规模被格式钉死（4 段 × 3 位），模板四件套清晰可见，而真正的思考量在
剪枝的分层 —— "这一段行不行"与"这条路有没有戏"是两个独立的问题，混在一起写要么漏剪要么剪错。把这两层分开，同族的分割题、组合题都是换汤不换药。