标签：回溯 中等
# 题目
有效 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"]
1
2
2
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
1
2
2
示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
1
2
2
提示：
- 1 <= s.length <= 20
- s 仅由数字组成
# 解析
第一个分割问题看的有点懵里懵懂，不知道为什么分割问题可以用回溯来解决，做第二个分割问题的时候有点感觉了。其实分割问题和组合问题类似，都是在一个集合中找组合，只不过分割中元素的必须是相连的，而组合中是挑选集合中的一些数组成集合。
从代码找思想：
- for循环是为了找到从初始值
startIndex开始到i的这一段字符串是否满足题目要求，s[startIndex...i]就是一个切割位置 - 递归找到所有的切割位置，因为每个部分都是相连的，找下一个切割位置时，让
i=startIndex+1继续开始上述切割过程 - 使用题目条件作为递归出口，判断切割方案是否满足
有一句话很形象：回溯就是穷举，在穷举出的二叉树中，for循环就是遍历同一层的不同情况，而递归就是在上一层的情况下继续迭代下一层，直到递归出口判断是否满足条件。
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
let res = [], temp = [];
backtracing(0);
return res;
function backtracing(startIndex) {
if(temp.length === 4 && startIndex >= s.length) {
res.push(temp.join('.'));
return ;
}
for(let i=startIndex; i<s.length && temp.length<4; i++) {
let str = s.slice(startIndex, i+1);
// 如果s[startIndex...i]已经不符合条件了，说明s[startIndex...]更不符合，所以可以直接break
if((i-startIndex>0 && s[startIndex]==0) || parseInt(str)>255) break;
temp.push(str);
backtracing(i+1);
temp.pop();
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23