有效 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 = "1111"
输出：["1.1.1.1"]示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]思路回溯算法
# @lc app=leetcode.cn id=93 lang=python3
#
# [93] 复原 IP 地址
#
#回溯算法：
# void backtracking(参数) {
# if (终止条件) {
# 存放结果;
# return;
# }
# for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
# 处理节点;
# backtracking(路径，选择列表); // 递归
# 回溯，撤销处理结果
# }
# }
# @lc code=start
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def backtracking(n,now,k,rev):
if k==1:
if n-now in range(1,4) and str(int(s[now:n]))==s[now:n] and int(s[now:n]) in range(0,256):
res.append(rev+s[now:n])
return
for i in range(1,4):
if now+i<n and str(int(s[now:now+i]))==s[now:now+i] and int(s[now:now+i]) in range(0,256):
now=now+i
backtracking(n,now,k-1,rev+s[now-i:now]+".")
now=now-i
# s = "25525511125"
rev=str()
res=list()
backtracking(len(s),0,4,rev)
return res
# @lc code=end
