```
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
res = []
path = ["" for i in range(4)]
self.dfs(s,0,path,res)
return res
def dfs(self, s, level, path, res):
#base case
if not s:
return
#terminate & check valid
if level == 3:
path[level] = s
if len(path[level]) <= 3 and str(int(path[level])) == path[level] and int(path[level]) <= 255:
res.append('.'.join(path))
return
#try all possible combinations
for i in range(1,4):
path[level] = s[:i]
if str(int(path[level])) == path[level] and int(path[level]) <= 255:
self.dfs(s[i:],level+1,path,res)
```