93.复原IP地址

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址。

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

1. dfs+回溯+剪枝。当前字符串合法(两位以上不含有前导0且数值小于255)则加入结果，加入结果前要判断剪枝，如果当前字符串后面的字符串长度不在剩余未插入IP块数量一倍到三倍数量范围之内，那么直接continue(注意这里不能直接return回溯调整前一个IP块字符串，因为可能当前字符串长为1的时候不满足，但是当长为2的时候就满足,剪枝是剪去当前这个字符串的可能性，而不是当前这个IP块的可能性)。

• 当前字符串含有前导0或者是当前字符串长超过3(一个IP块最多只有三位)则回溯到前一个IP块，回溯前还要在容器path保存的IP地址中取出当前字符串,path.remove(num)。
• 每次递归都要修改当前字符串的下标index和当前IP块号。

public void addIP(List<String> res,List<Integer> path,String s,int num,int index)
    {
        if(num==4)
        {
          if(index==s.length())
      res.add(new String(String.valueOf(path.get(0))+"."+String.valueOf(path.get(1)) +"."+String.valueOf(path.get(2))+"."+String.valueOf(path.get(3))));
        return ;  
        }
        for(int i=0;i<3;i++)
        {
            if((s.length()-index-i-1<3-num||s.length()-index-i-1>3*(3-num)))
            continue ;
            else
            {
                int sum=0,j=0;
                while(j<=i) 
                {
                  sum=sum*10+(s.charAt(index+j)-'0'); 
                  j++; 
                }
                if(sum>255)
                return ;
                if(s.charAt(index)=='0')
                {
                    sum=0;
                    path.add(sum);
                    addIP(res,path,s,num+1,index+1);
                    path.remove(num);
                    return ;
                }
                path.add(sum);
                addIP(res,path,s,num+1,index+i+1);
                path.remove(num);
            }
        }
    }