题目描述
思路解析动画文字版
关键不是背模板，而是看懂为什么这题适合回溯 · 分段。
1. 候选 = s 的 6 位数字，要切成 4 段：候选行就是字符串 101023 的 6 位数字。回溯目标：依次切出 4 段，每段 0 到 255、无前导零，且刚好用完全部数字。当前 path 为空，结果集为空。
2. 第 1 段：先试长度 1，取数字 1：从下标 0 开始，先尝试最短的 1 位段：候选 "1"。橙框标出正在试的起始数字。
3. 校验 "1"：无前导零且 1 ≤ 255，合法："1" 不以 0 开头、数值 1 在 0 到 255 内，合法。把它加入 path，第 1 位数字标记为已用（变灰），递归去切第 2 段。
4. 第 2 段：取数字 0，单独的 0 合法：第 2 段从下标 1 取 1 位 "0"。单个 0 是允许的（只有 0X 这种才算前导零非法）。path 变为 1 → 0，前两位已用。
5. 第 3 段试长度 1：候选 "1"：第 3 段从下标 2 开始，先试 1 位 "1"。橙框落在下标 2。注意：若第 3 段只用 1 位，剩下 023 三位要塞进第 4 段，而 "023" 有前导零会被否决——所以这条 1 位分支最终走不通。
6. 改试第 3 段长度 2：候选 "10"，合法：第 3 段改取 2 位 "10"：无前导零、10 ≤ 255，合法。下标 2、3 标记已用，path 变为 1 → 0 → 10。
7. 第 4 段：剩下的 "23" 必须刚好用完：已凑满 4 段，第 4 段拿剩余 "23"：23 ≤ 255 合法，且下标走到 6 = 字符串末尾，6 位全部用完。这是一个完整合法 IP。
8. 收集第 1 个答案 1.0.10.23：把 1 → 0 → 10 → 23 拼成 1.0.10.23 收入结果集。然后弹出第 4 段，回溯到第 3 段，尝试别的切法。
9. 回溯第 3 段：弹出 "10"，改试长度 3 "102"：弹出 "10"，第 3、4 位重新变为未用，path 退回 1 → 0。第 3 段改试 3 位 "102"：橙框回到下标 2，准备校验。
10. "102" 合法，第 4 段取 "3"，得第 2 个答案："102" ≤ 255 合法，第 4 段拿剩余 "3" 也合法且用完。拼出 1.0.102.3 收入结果集，已有 2 个答案。
11. 回到第 1 段：弹空 path，改试第 1 段长度 2 "10"：以 "1" 开头的分支全部试完，回溯到最外层：清空 path、所有数字复位。第 1 段改试 2 位 "10"，开启全新一组切法。
12. "10" 合法，深入后又得 2 个答案：第 1 段取 "10"（下标 0、1 已用）后继续回溯，这条分支又找出 10.1.0.23 与 10.10.2.3 两个合法 IP，结果集累计到 4 个。
13. 第 1 段试长度 3 "101"：剪枝演示，先看非法的 "010"：第 1 段取 3 位 "101" 合法。但深入后第 2 段若从下标 1 取 3 位会得到 "010"——以 0 打头的多位段非法，红叉剪掉。这就是前导零剪枝。
14. 同分支收下最后一个答案 101.0.2.3：第 1 段 "101" 后，第 2 段取单个 "0"、第 3 段 "2"、第 4 段 "3" 全合法且用完，拼出 101.0.2.3。结果集达到 5 个。
15. 剪枝总结：超过 255 与长度越界都被砍：若候选段数值大于 255（如 "256"）或前导零（如 "010"），立刻回退不再深入；若已切 4 段但还剩数字、或不到 4 段已没数字，同样作废。靠这些剪枝，搜索空间被大幅压缩。
16. 全部分支走完，输出 5 个合法 IP：第 1 段长度 1、2、3 三条主干分支全部回溯完毕，最终收集到 5 个合法地址：1.0.10.23、1.0.102.3、10.1.0.23、10.10.2.3、101.0.2.3。
把这句话记住，下次遇到同类题，就能更快选出方向。
参考代码
class Solution: def restoreIpAddresses(self, s): ans = [] def ok(part): return str(int(part)) == part and 0 <= int(part) <= 255 def backtrack(i, path): if len(path) == 4: if i == len(s): ans.append('.'.join(path)) return for l in range(1, 4): if i + l <= len(s): part = s[i:i+l] if ok(part): path.append(part) backtrack(i + l, path) path.pop() backtrack(0, []) return ans复杂度
- 时间复杂度：O(1)，段数固定为 4、每段长度只在 1 到 3 取值，分支总数被常数 3^4 = 81 封顶，与串长无关
- 空间复杂度：O(1)，递归深度恒为 4 段，path 最多存 4 个段，辅助空间为常数（不计输出）
可套用的代码模板
模板不是死背，而是提醒你写代码前先把状态、转移和边界排好。
Python
# 回溯 · 分段 通用检查表# 1. 定义状态/指针/容器# 2. 每轮只做一个清晰动作# 3. 更新答案并处理边界易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分割回文串
LeetCode 131 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题