问题93：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于0到255之间组成），整数之间用 '.' 分隔。
这题用回溯法，把输入的字符串分成四个字串。这题的难度是，有很多限制条件，比如每部分不能以0开头，且不能大于255，长度必须在1和3之间。
完整代码：
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
ans = []
def backtracking(l, num):
if num == 0:
if not ((len(l[-1]) > 1 and l[-1][0] == '0') or int(l[-1]) > 255):
ans.append('.'.join(l))
return None
for i in range(0, 3):
if (len(l[-1]) - (i+1)) / num > 3:
continue
elif (len(l[-1]) - (i+1)) / num < 1:
break
elif int(l[-1][:i+1]) > 255 or (l[-1][:i+1][0] == '0' and len(l[-1][:i+1]) > 1):
continue
l.insert(-1, l[-1][:i+1])
l[-1] = l[-1][i+1:]
num -= 1
backtracking(l, num)
num += 1
l[-1] = l[-2] + l[-1]
l.pop(-2)
backtracking([s], 3)
return ans
运行结果：
