题目描述给定一个只包含数字的字符串s用它来表示一个 IP 地址返回所有可能的有效 IP 地址。有效 IP 地址规则由4 段整数组成每段用.分隔。每段整数的取值范围0 ~ 255。每段整数不能有前导 0除非该段本身就是 0如0是合法的01不合法。不能重新排序或删除s中的任何数字。示例 1输入s 25525511135输出[255.255.11.135,255.255.111.35]示例 2输入s 0000输出[0.0.0.0]核心思路回溯法IP 地址需要被分成 4 段每段长度为 1~3 位数字且满足上述规则。我们可以用回溯法枚举所有可能的分割方式同时用剪枝排除无效分支。回溯三要素选择在当前位置选择截取 1 位、2 位或 3 位数字作为一段。限制剪枝截取的子串长度不能超过 3也不能超出字符串末尾。子串代表的数字必须在0~255之间。子串长度大于 1 时不能以0开头前导 0 非法。结束条件已经分割出 4 段且用完了所有字符将当前方案加入结果集。完整代码实现C#include vector #include string using namespace std; class Solution { public: vectorstring restoreIpAddresses(string s) { vectorstring result; vectorstring path; // 保存当前分割的4段 backtrack(s, 0, path, result); return result; } private: // start: 当前处理的起始位置 // path: 已经分割出的段 void backtrack(const string s, int start, vectorstring path, vectorstring result) { // 终止条件已经分割出4段且用完了所有字符 if (path.size() 4) { if (start s.size()) { // 将4段用.拼接成IP地址 string ip path[0] . path[1] . path[2] . path[3]; result.push_back(ip); } return; } // 枚举当前段的长度1~3位 for (int len 1; len 3; len) { // 剪枝1超出字符串长度 if (start len s.size()) break; // 截取当前段 string segment s.substr(start, len); // 剪枝2前导0长度1且以0开头 if (len 1 segment[0] 0) break; // 剪枝3数值超过255 if (stoi(segment) 255) break; // 选择当前段 path.push_back(segment); // 递归处理下一段 backtrack(s, start len, path, result); // 回溯撤销选择 path.pop_back(); } } };代码逐行详解1. 主函数与初始化vectorstring restoreIpAddresses(string s) { vectorstring result; vectorstring path; backtrack(s, 0, path, result); return result; }result存放所有合法的 IP 地址。path存放当前正在构建的 4 段 IP 地址。从start0开始递归分割。2. 终止条件if (path.size() 4) { if (start s.size()) { string ip path[0] . path[1] . path[2] . path[3]; result.push_back(ip); } return; }当path.size() 4时说明已经分割出 4 段。此时需要start s.size()表示所有字符都已用完这才是一个合法的 IP 地址。不满足start s.size()说明字符没用完是无效分支直接返回。3. 枚举分割长度 剪枝for (int len 1; len 3; len) { // 剪枝1超出字符串长度 if (start len s.size()) break; string segment s.substr(start, len); // 剪枝2前导0长度1且以0开头 if (len 1 segment[0] 0) break; // 剪枝3数值超过255 if (stoi(segment) 255) break; // ... 递归与回溯 }len表示当前段的长度只能是 1~3 位。剪枝 1如果start len超出字符串长度直接 break更长的len也会超出无需继续循环。剪枝 2如果段长度大于 1 且以0开头如01不合法直接 break。剪枝 3段的数值超过 255如256不合法直接 break。4. 递归与回溯path.push_back(segment); backtrack(s, start len, path, result); path.pop_back();path.push_back(segment)将当前合法的段加入路径。backtrack(s, start len, path, result)递归处理下一段起始位置变为start len。path.pop_back()回溯撤销当前段尝试下一种长度。示例推演以s 25525511135为例第一步分割第一段len12合法 → 递归处理start1len225合法 → 递归处理start2len3255合法 → 递归处理start3重点分支第一段为255start3第二步分割第二段start3len12合法 → 递归处理start4len225合法 → 递归处理start5len3255合法 → 递归处理start6分支第二段为255start6第三步分割第三段start6len11合法 → 递归处理start7len211合法 → 递归处理start8len3111合法 → 递归处理start9分支 1第三段为11start8第四段截取len3135数值 135 ≤ 255合法四段为[255,255,11,135]→ 拼接为255.255.11.135加入结果。分支 2第三段为111start9第四段截取len235数值 35 ≤ 255合法四段为[255,255,111,35]→ 拼接为255.255.111.35加入结果。复杂度分析时间复杂度\(O(3^4 \times n) O(1)\)常数级每段有 3 种长度选择共 4 段最多 \(3^481\) 种分割方案。每个方案需要 \(O(n)\) 时间拼接 IP 地址\(n \leq 12\)实际影响可忽略。空间复杂度\(O(4) O(1)\)递归栈深度为 4分割 4 段path数组长度为 4均为常数级。关键知识点总结核心思想用回溯法枚举所有分割方案用剪枝排除无效分支。三大剪枝技巧长度剪枝段长度 1~3且不超出字符串末尾。前导 0 剪枝长度 1 时不能以0开头。数值剪枝段的数值必须 ≤ 255。终止条件分割出 4 段且用完所有字符。