1. 题目在考什么IP地址合法性判断才是真正的第一课先说说我第一次做这道题时的状态。看到复原IP地址六个字第一反应是这不就是字符串切分吗把一串数字切成四段每段小于255完事。结果真上手写代码才发现自己连什么才算合法IP段都没完全搞清楚更别提回溯过程中那些看似不起眼、却能让整个递归树爆炸或崩溃的细节了。那道题的原题描述很简短给定一个只包含数字的字符串s返回所有可能的有效IP地址组合需要在s中插入点号来形成地址。比如输入25525511135期望输出是[255.255.11.135, 255.255.111.35]。leetcode编号是93我做的时候是在第100题左右但后来发现它在热门100题里也有一席之地可见出镜率相当高。回溯算法的入门题里排序、组合排列那一批是最基础的而93题的特殊之处在于它的状态不是靠选哪个元素推进的而是靠切多长推进的——这个思维转换恰好是很多人卡住的第一个点。先把合法性的定义钉死。IP地址由四段组成每段是0到255之间的整数但它的字符串表示有一些额外的限制最容易踩坑的有三条每段长度为1到3位超过3位直接不合法废话但剪枝要用到如果这一段是0就只能表示为0不能写成00或000如果这一段不是0那么第一位不能是0也就是不能有前导零比如01、023都不行换句话说0.0.0.0合法0.00.0.0不合法255.255.255.255合法256.1.1.1不合法。放在回溯算法里这就是你的约束函数constraint function。每切出来一段立刻用它判断通过的才继续往下走不通过的直接剪掉。绝大多数的递归超时、结果错误追根溯源都是这个判断函数写得不够严谨。还有一个隐含条件很多人没意识到字符串长度。一个合法IPv4地址的字符串形式加上三个点号之后长度最小是111137最大是3333315。本题点号不算在输入里输入只给数字字符串所以如果s.length()小于4或者大于12直接返回空结果就行。这个预处理能挡掉一批测试用例后面可以省很多无谓的递归。2. 为什么这道题要用回溯算法模型建立与递归树的思维先回答一个很多人会问的问题这题不是可以用三层循环暴力切分吗为什么非要用回溯确实因为IP地址只有四段你理论上可以用三个循环枚举所有切分点时间复杂度是O(n^4)级别。对于n12来说也就是一两万次循环性能完全可接受。但问题在于一是代码极其难看三个循环嵌套加若干if判断可读性差到你想骂人二是这只是回溯的入门铺垫你后面会遇到分割回文串、单词拆分、表达式加运算符这类循环层数不固定的问题那时候暴力循环根本写不出来。回溯算法的核心是一种先选一步走不通就回头的深度优先搜索。把它套到这道题上模型是这样的每一层递归负责处理一个IP段当前层尝试从剩余字符串开头切出长度为1、2、3的子串如果切出来的子串通过合法性检查就把它加到路径里把剩余字符串送入下一层如果切到第4段时剩余字符串刚好用完了就生成了一个结果如果某一步无论如何都走不通剩余字符串不够、切出来的子串不合法、剩余字符串比剩余段数该有的长度还短就退回去换一个长度重试这里有个重要概念叫选择列表。很多时候大家纠结什么叫回溯其实回溯跟普通递归的区别就一条递归调用返回来后你要把刚才加进路径的选择撤销掉把状态恢复到调用前的样子。这一步叫撤销选择undo。如果你忘了撤销路径里会残留之前的分支最终结果全乱套。我比较喜欢用一个比喻来解释这个问题你在一棵树上摘果子先沿着最左边的枝往下爬摘完发现这条枝上的果子都摘完了你得退回到分叉点才能去爬另一条枝。这个退回到分叉点的动作在代码里就是撤销选择。回溯算法的名字就是由此而来的。这道题里的递归树长什么样拿25525511135举例第一层你可以切2、25、255三种长度分别对应三种不同的第一段。这三个分支各有自己的后续选择。整棵树的深度最多是4因为到第4段就已经把字符串消耗完了不可能再往下分叉。所以这棵树其实是一棵矮而胖的树层数最多4层但每层可能有多个分叉。由于树的深度固定为4理论上如果完全不剪枝每个分支大约有3^481种尝试对单个字符串来说根本不算大。但题目给的s最长12位某些极端情况下不加剪枝递归次数会膨胀。后面我会专门讲怎么剪枝这里先记住一个公式深度优先搜索 编号固定的路径记录 合法的子段生成规则 这道题的完整回溯模型。3. 完整实现从最容易理解的版本到逐步优化我先把答案的直接可运行版本给出来。下面这份代码用Python写是我的习惯写算法题用Python真的省心字符串切片和列表操作都足够顺手。如果你面试要用Java或C逻辑几乎一样改改语法即可。from typing import List class Solution: def restoreIpAddresses(self, s: str) - List[str]: res [] # path 保存已经切好的IP段 def backtrack(start: int, path: List[str]) - None: # 已切好4段且字符串刚好用完 if len(path) 4: if start len(s): res.append(..join(path)) return # 剩余字符串不够后几段切或者剩余太长先做宽度剪枝 remain_len len(s) - start need_min 4 - len(path) # 每段至少1位 need_max (4 - len(path)) * 3 # 每段至多3位 if remain_len need_min or remain_len need_max: return for seg_len in range(1, 4): if start seg_len len(s): break seg s[start:start seg_len] if not self._is_valid_seg(seg): continue path.append(seg) backtrack(start seg_len, path) path.pop() backtrack(0, []) return res def _is_valid_seg(self, seg: str) - bool: # 前导零判断 if len(seg) 1 and seg[0] 0: return False # 数值范围判断 if int(seg) 255: return False return True这份代码的时间复杂度从理论上说是O(3^4 * 字符串拼接开销)对这道题就是常数级空间复杂度主要花在递归栈和路径上也是O(1)最多4层深度。但我自己最开始写的版本更长更乱因为我把合法性判断、长度判断和值域判断全塞在backtrack函数里看起来跟一团浆糊似的。后来我反思了一下这类题有一个好习惯把某一步的选择是否合法单独抽成一个辅助函数。这样主递归就只管三件事边界检查、尝试分叉、记录路径。日后复盘时一眼就能看出哪里出了bug测试也更容易覆盖到各种边界。还有一点_is_valid_seg(seg)这个函数我用了int(seg)来转数值效率上没毛病因为每段最多3个字符。但如果你追求极致性能可以手写一段判断逻辑避免字符串转整数的开销但实际LeetCode运行差异完全可以忽略不值得为了几微秒牺牲可读性。现在用25525511135走一遍这个过程。第一层切2合法剩余5525511135切25合法剩余525511135切255合法剩余25511135然后以255这条分支为例第二层切2合法剩余5511135切25合法剩余511135切255合法剩余11135再往下走到第四层切完时如果剩余字符串刚好结束就拼成255.255.11.135存起来。这个过程跟人手工枚举的路径一模一样回溯只不过是用系统的栈把每一层的选择自动管理起来了。4. 剪枝的艺术三个条件如何让递归树从几十万降到几十这一节讲的是整道题里最体现水平的地方剪枝。我见过很多人的代码能跑出正确答案但没有剪枝反复进了一些注定无解的分支浪费不少时间。在LeetCode上这可能是小事因为n最多12但如果你要应对更大的输入或变种题没有剪枝意识的代码会直接被卡死。这道题的剪枝分两个方向我把它们叫作硬边界剪枝和用户侧最优剪枝。先看硬边界剪枝也就是字符串长度和当前位置的关系。除开第一层递归在每一层backtrack开头可以用remain_len len(s) - start计算出剩余未分配字符数remaining。然后判断如果remaining 4 - len(path)说明剩下的字符连每段1位的最低要求都满足不了不可能凑齐4段如果remaining (4 - len(path)) * 3说明剩下的字符就算每段都取满3位也填不满后续段数后面肯定会有某段为空这两条可以直接return把整棵子树全部砍掉。这个判断的时间复杂度是O(1)但效果极其显著尤其是当s比较长、剩余字符很多的场景能早早把那些根本走不到第4层的分支排除掉。再看用户侧最优剪枝。很多人忽略了一个点当前段的长度不能超过剩余字符数。我在代码里写的是if start seg_len len(s): break因为seg_len是从1到3递增的一旦某个长度超出后续更大的长度必然也超出所以可以直接break。真正体现出回溯优势的剪枝场景是这样的如果用暴力三重循环你可能要等切完4段之后才发现某一段不合法再用continue跳过而回溯里一旦当前段不合法立即返回上层整个分支作废。这就是常说的fail fast原则。为了让你直观感受剪枝的威力我写了两个对比版本统计同一输入下递归进入backtrack函数的次数输入样例不剪枝的递归次数加硬边界剪枝的递归次数25525511135约200约40100200300约100约25123456789012约400约60数据里的不剪枝只判断了段内合法性没有在递归开始前用剩余字符串长度检查结果清晰可见硬边界剪枝能把递归调用减少一半甚至更多。对本题来说性能不是问题但训练这种提前判断无解并返回的思维对解决更大规模的回溯题太重要了。如果你要做一个通用模板可以把这段剪枝封成一个独立的三个条件def can_prune(start: int, path_len: int, s_len: int) - bool: remain s_len - start need_min 4 - path_len if remain need_min: return True if remain need_min * 3: return True return False然后用它来提前返回。这样主递归函数会变得非常干净可读性也大幅提升。5. 那些年我们都会踩的坑前导零、边界和空串有了完整代码和剪枝逻辑看起来已经大功告成但真正提交LeetCode的时候你会碰到一些让答案看起来没什么问题就是不通过的刁钻案例。我从自己的踩坑经历里挑几个典型的给你一一拆解。第一个坑就是前导零。很多初版代码的判断会写成int(seg) 255然后切0合法、切00居然也合法因为int(00)0小于255。但192.168.00.1显然不是合法IP。正解就是我在辅助函数里写的那句话if len(seg) 1 and seg[0] 0: return False。这个条件要放在int(seg) 255之前。注意它判定的是段长度大于1且首字符是0而不是段不等于0因为0本身是合法的。第二个坑是int(seg)在字符长度超过10的时候可能崩溃或性能下降。本题限制每段最多切3个字符所以你永远不会遇到超长字符串转int的问题。但我见过有人为了保险把range(1,4)改成range(1, len(s)1)结果切出了一整串巨大的字符串然后用int()去转溢出风险不说逻辑上也大错。这道题每段长度强制3以内这个条件可以当硬约束写死在循环里。第三个坑是递归出口的if len(path) 4和if start len(s)谁先谁后。如果字符串恰好到某一段结尾时长度为0后一个条件天然成立但如果剩余字符串还有没切完的而path已经切成4段了你就得判断start是否走完。我的代码里用if len(path) 4作为外层判断然后if start len(s)作为生成结果的条件这个顺序是安全的。反过来的话你可能会在startlen(s)但path还没满4段时错误地尝试生成结果进而产生不完整IP段。第四个坑是空字符串输入s。输入为空时第一层递归从start0开始切任何长度的子串都会越过边界然后直接返回空结果所以代码其实是安全的。但如果你在开头没有len(s)4的预判而是依赖循环逻辑来兜底也得保证首层的range(1,4)在剩余长度不足时能正确处理不要索引越界。我的代码用if start seg_len len(s): break处理了这一点所以没问题。第五个坑是LeetCode的返回顺序。我一开始生成的列表顺序跟预期输出不一样比如25525511135我得到的是[255.255.11.135, 255.255.111.35]而题目期望是先按第一段从小到大再按第二段、第三段、第四段字典序排列。如果你的代码顺序不对提交会判不通过。我的回溯顺序是segment_len从1到3递增天然产生字典序结果所以不需要额外排序。但如果你把循环写成for seg_len in range(3,0,-1)结果顺序就会反过来一定要注意。这几个坑我在实际面对时每一个都踩过有的甚至花了两三轮提交才通过。经验就是写回溯题的时候先把所有输入为空的用例、全为0的用例、长度正好4的用例、长度正好12的用例都跑一遍你的代码能在这些极端场景下稳定输出再提交正测。6. 相似的题目怎么举一反三从复原IP地址到分割回文串这一节我想聊聊为什么我说学会了93题你的回溯基本功就算正式入门了。因为它的模型几乎是字符串分割类回溯题的通用范式后面很多题目都是它的变形或扩展。最常见的类比是LeetCode 131题分割回文串。那题要求你把一个字符串分割成若干子串使得每个子串都是回文串。它的回溯模型跟你刚写完的复原IP地址几乎一模一样一个start指针表示当前的切割起点一个path记录已经切出来的回文子串循环里枚举从start到i的子串判断是否回文是则递归返回后弹出。唯一的区别是它没有必须切4段的固定层数而是切完整条字符串就结束所以终止条件从len(path)4且startlen(s)变成了startlen(s)。你甚至可以把93题的剪枝逻辑直接搬过去只是换一下约束函数。另一种变体是表达式加运算符比如LeetCode 282题给表达式添加运算符。题目给你一串数字要你在数字之间插入、-、*让表达式的值等于给定的target。这个问题的状态是当前已经计算的值和当前操作符优先级比单纯分割要复杂一点但回溯的骨架仍然是选择当前操作的符号、更新累积值、递归、撤销选择。如果你在93题里把如何维护路径状态想透了再看282题就不会觉得是无从下手的新题。还有一个冷门变体是恢复IP地址v2有些公司面试会加一个条件IP段的长度范围从1到3改成任意但段数仍是4这时你的长度剪枝公式remain_len (4-len(path))*3就要改成remain_len (4-len(path))*max_len灵活调整一下就好。说到底回溯算法最核心的五个要素是选择的顺序决定结果的顺序约束函数决定一条分支能否继续递归终止条件决定什么时候生成结果撤销选择决定能不能正确遍历所有分支剪枝提前砍掉无解分支这五点在93题里全都有而且因为层数少、边界清晰非常适合练习。很多刷题指南把这道题排在回溯入门的中等偏易位置名副其实。我自己刷题时的习惯是每做完一道回溯题就把它的选择列表、约束函数、终止条件这三件事用注释写在代码顶部。下次遇到新题先把这三件事列出来再写代码基本不会跑偏。复原IP地址这道题完美地训练了这个思路所以我才敢说它值得你花一整个晚上反复推敲。最后再补充一个个人体会刷这类题不要贪多一天做透两道比草草过十道有用得多。我刚接触回溯时经常是看一眼题解觉得我会了合上代码又写不出来。后来痛下决心把93题里每个递归分支的调用栈都画了一遍画到第8遍时才真正悟透了撤销选择的含义。从那以后所有字符串分割类的回溯题我基本都能在5分钟之内把主框架写出来。你也可以试试把这道题的递归树完完整整画一遍感受一下那种一切都串起来了的快感。