递归算法恢复ip地址

给定一个只包含数字的字符串，用以表示一个 IP 地址，要求恢复出所有可能的 IP 地址。这是一个典型的回溯算法问题，可以通过递归实现。具体步骤如下：

1. 定义一个数组 `segments`，用于存储 IP 地址的四个段；
2. 定义一个变量 `start`，表示当前处理到字符串的哪个位置；
3. 定义一个变量 `segmentCount`，表示已经处理了几个段；
4. 如果已经处理了四个段并且字符串已经处理完毕，则将 `segments` 中的四个段拼接成一个 IP 地址，并将其加入结果集；
5. 如果已经处理了四个段但字符串还没有处理完毕，则直接返回；
6. 如果还没有处理完四个段但字符串已经处理完毕，则直接返回；
7. 对于每个段，从 `start` 开始，枚举可能的结束位置，如果这个段合法，则将其加入 `segments` 数组中，并递归处理下一个段；
8. 处理完当前段后，需要将 `segments` 数组中的当前段删除，以便处理下一个可能的结束位置。

代码如下（Python实现）：

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(start: int, segmentCount: int):
            if segmentCount == 4:
                if start == n:
                    ip = ".".join(str(seg) for seg in segments)
                    res.append(ip)
                return
            if start == n:
                return
            if s[start] == "0":
                segments[segmentCount] = 0
                backtrack(start + 1, segmentCount + 1)
            addr = 0
            for end in range(start, n):
                addr = addr * 10 + int(s[end])
                if 0 < addr <= 255:
                    segments[segmentCount] = addr
                    backtrack(end + 1, segmentCount + 1)
                else:
                    break

        n = len(s)
        if n < 4 or n > 12:
            return []
        segments = [0] * 4
        res = []
        backtrack(0, 0)
        return res