复原 IP 地址（回溯+剪枝）

力扣地址：力扣

        有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

        例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
        给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

1 <= s.length <= 20
s 仅由数字组成

示例代码：

class Solution(object):
    def restore_ip_address(self, s):
        res = []
 
        def back_tracing(start, tmp):
            if len(tmp) > 4:
                return
            if start == len(s) and len(tmp) == 4:
                res.append('.'.join(tmp))
 
            for i in range(start, len(s)):
                # if int(s[start: i+1]) > 255 or s[start] == '0' and len(s[start: i+1]) >= 2: # 等价下述写法
                if int(s[start: i+1]) > 255 or (s[start] == '0' and len(s[start: i+1]) >= 2):
                    return
                tmp.append(s[start: i+1])
                back_tracing(i+1, tmp)
                tmp.pop()
 
        back_tracing(0, [])
        return res
 
 
s = "25525511135"
s = "0000"
obj = Solution()
res = obj.restore_ip_address(s)
print(res)

思路解析：  【回溯+剪枝】

• 步骤1：先想清楚这种字符串如何取出数字，以便可以通过递归取出所有可能的数字        
• 步骤2：在字符串里，截取不同长度的字符，需要s[start:i+1]来取，因为不像纯数字列表，每种情况直接可以拿到[1， 23， 4]        
• 步骤3：何时添加到结果？start到终点位置，且也找到了4个数，即添加结果        
• 步骤4：剪枝操作：

        1.当截取的字符转换为数字后的值大于255，且出现为'06'这样的不合法情况                    

         2.当取的数大于4的时候，不符合IP的格式，直接返回