```
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
def is_solution(a, k, n, s, sols):
# dotted decimal notations will have 4 numbers
# entire string has been consumed
return k == 4 and n == len(s)
def process_solution(a, k, n, s, sols):
# prepare dotted decimal notations
sols.append('.'.join(a))
def construct_candidates(a, k, n, s, sols):
candidates = []
if len(s) >= 3 and int(s[:3]) <= 255 and s[:3][0] != '0': # ignore with preceeding 0, numbers > 255
candidates.append(s[:3])
if len(s) >= 2 and int(s[:2]) <= 255 and s[:2][0] != '0': # ignore with preceeding 0, numbers > 255
candidates.append(s[:2])
if len(s) >= 1 and int(s[:1]) <= 255: # can't strip off preceeding 0 if there is only one digit
candidates.append(s[:1])
return candidates
def backtrack(a, k, n, s, sols):
if is_solution(a, k, n, s, sols):
process_solution(a, k, n, s, sols)
else:
candidates = construct_candidates(a, k, n, s[n:], sols)
k = k + 1
for candidate in candidates:
a.append(candidate)
n = sum(map(len,a))
backtrack(a, k, n, s, sols)
a.pop()
if len(s) > 12:
return []
a = []
k = 0
sols = []
backtrack(a,k,0,s,sols)
return sols
```