from CodeTop, Leetcode, 93. 复原IP地址。
深度优先暴力搜索，和全排列相似的思路
题意：
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ’.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = “25525511135”
输出：[“255.255.11.135”,”255.255.111.35”]
示例 2：
输入：s = “0000”
输出：[“0.0.0.0”]
示例 3：
输入：s = “101023”
输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]
解读：
和全排列思路一样，使用深搜暴力搜索，确定三个变量：
- 当前走到了原字符串的第几位
- 当前正在生成 ip 地址的第几个整数
- 当前的 path （ip 地址）是什么
代码及注释：
vector<string> ans; // 存储结果
vector<string> restoreIpAddress(string& s){
if (s.size() > 12) return {};// 如果源字符串超过12位，显然无法组成 IP 地址
dfs(s, 0, 0, "");
return ans;
}
void dfs(string& s, int u, int k, string path){
// u: 当前走到原字符串的第几位字符（从 0 开始）
// k: 现在在生成的是 ip 地址的第几个整数（从 0 开始）
if (u == s.size() && k = 4){ // 遍历完原字符串，也正好生成了 4 个整数
path.pop_back(); // 最后还有一个点，去掉它。
ans.push_back(path);// 加入结果集
return;
}
if (u == s.size() || k == 4) return;
// 剪枝。两个条件都满足的情况就是成功加入届国际的条件，这里只能是两个条件满足
// 且只满足一项，也即必然有一项不满足，显然无法继续找下去，直接 return
for (int i = u, t = 0; i< s.size() && i < u+3; i++){
// i 是遍历到原字符串的位置，显然不能超过起始点三位。
// t 是当前整数的值
if (i > u && s[u] == '0') break; // 前导是零，直接 break
t = t*10 + s[i] - '0';
if (t < 256) dfs(s, i+1, k+1, path + to_string(t) + '.');
// 当且仅当当前整数的值合法（不大于256），继续走到下一位寻找下一个整数
}
}
