Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Example 1:

Input: s = "25525511135"Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"Output: ["0.0.0.0"]

Example 3:

Input: s = "1111"Output: ["1.1.1.1"]

Example 4:

Input: s = "010010"Output: ["0.10.0.10","0.100.1.0"]

Example 5:

Input: s = "101023"Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

• 0 <= s.length <= 3000
• s consists of digits only.

### Analyze

/** * @param {string} s * @return {string[]} */var restoreIpAddresses = function (s) {  const arr = []  for (let i = 1; i < 4; i++) {    for (let j = i + 1; j < i + 5; j++) {      for (let z = j + 1; z < j + 5; z++) {        const a = s.slice(0, i)        const b = s.slice(i, j)        const c = s.slice(j, z)        const d = s.slice(z, s.length)        if (validate(a) && validate(b) && validate(c) && validate(d)) {          arr.push(${a}.${b}.${c}.${d})        }      }    }  }  return arr};
var validate = function (value) {  if (value.length > 3 || value.length === 0 || +value > 255 || (value[0] === '0' && value.length > 1)) {    return false  }  return true}

/** * @param {string} s * @return {string[]} */var restoreIpAddresses = function(s) {  const res = []  backtracking(s, 0, '', res)  return res};
var backtracking = function(s, start, ipValue, res) {  const splitIpNode = ipValue.split('.')  const ipNode = splitIpNode.length  // end condition  for (let i = 0; i < ipNode; i++) {    if (!isValid(splitIpNode[i])) return  }  if (ipValue.length === s.length + 3 && !ipValue.endsWith('.')) {    // 比如 010010 存在两种相等的 case, 0100 + 1 + 0, 0100 + 10, 因此需要去重    if (res.indexOf(ipValue) === -1) res.push(ipValue)    return  } else if (ipValue.length === s.length + 3 && ipValue.endsWith('.')) {    return  }
for (let i = start + 1; i < start + 4; i++) {    if (i >= s.length + 1) return    const str = s.slice(start, i)    const ipValueNew = ipNode <= 3 ? ipValue + str + '.' : ipValue + str    backtracking(s, i, ipValueNew, res)  }}
// judge if the str value is valid for ip.var isValid = function (value) {  if (value.length > 3 || +value > 255 || (value[0] === '0' && value.length > 1)) {    return false  }  return true}