```
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if len(s) > 12: return []
Solution.res = []
self.genIp(s, "", 0, 0, 0)
return Solution.res
# cur: the candidate string
# val: the value of the current section
# pos: position of s
# n: how many '.' have we added
def genIp(self, s, cur, val, pos, n):
if val > 255: return
if n == 4 and pos == len(s):
Solution.res.append(cur[:-1])
return
val = 0
for i in xrange(1, min(4, len(s)+1-pos)):
num = s[pos: pos+i]
val = 10*val + ord(s[pos + i - 1]) - ord('0')
# Skip positive nums that start with 0 or numbers like 000
if i > 1 and num[0] == '0': return
self.genIp(s, cur + num + '.', val, pos + i, n+1)
```