将数字字符串转化为所有可能的IP组合，回溯法，递归求解 faster than 96%
遇到字符串的子序列或配准问题首先考虑动态规划，当需要求出所有可能情况首先考虑用递归。
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
var res = []
dfs(s, 0, [], res)
return res
};
var dfs = function(s, flag, sub, res){
var n = s.substring(flag).length
var k = 4 - sub.length
if(
(k === 1 && (n < 1 || n > 3))||
(k === 2 && (n < 2 || n > 6))||
(k === 3 && (n < 3 || n > 9))||
(k === 4 && (n < 4 || n > 12))
)
return
if (sub.length === 3) {
var str = s.substring(flag)
if(isValid(str)){
sub.push(str)
res.push(sub.join('.'))
sub.pop()
}
return
}
for(var i = flag; i < flag + 3; i++){
if(isValid(s.substring(flag, i + 1))) {
sub.push(s.substring(flag, i + 1))
dfs(s, i + 1, sub, res)
sub.pop()
}
}
};
var isValid = function(s){
if(s.length === 0 || s.length > 3 || s - '0' > 255) return false
if(s.length > 1 && s.charAt(0) === '0') return false
return true
};
