有效 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 中的任何数字。你可以按 任何 顺序返回答案。

题解

题解可参考liweiwei1419和代码随想录

一、判断IP是否合规（注意：这块需要每分割一个数就判断，这样有一个数不满足就递归终止，相当于剪枝）：

• 首先，字符串的长度小于 4 或者大于 12 ，一定不能拼凑出合法的 ip 地址

• 根据截取出来的字符串判断是否是合理的 ip 段，这里写法比较多，可以先截取，再转换成 int ，再判断：
  在0到255之间
  0开头的话只能是0.0.0.0(s.charAt(0)==‘0’&&s.length()!=1,return false)
  数目不等于四组，即num == 4（用num判断，而不需要用string.split()函数分割结果字符串）

二、利用回溯法找分割位置

• 终止条件：startIndex>=s.length()(分割位置越过数组长度，说明已经得到了一个满足条件的IP),path.add(temp)，这里要判断num==4,由于 ip 段就 4 个段，不满足不可以加入结果集
• 每层：限制i<=startIndex+2（剪枝，每一个结点可以选择截取的方法只有 3 种：截 1 位、截 2 位、截 3 位，因此每一个结点可以生长出的分支最多只有 3 条分支）和 i<s.length()
  （1）获得本次分割的数组：temp+s.substring(startIndex,i+1))+“.”,注意这里最后一个数字要特殊处理
  （2）判断是否有效，有效则继续进行分割，即进入下一层递归
  （3）分割数字的数目+1，即num++
  （4）回溯：num–
• 递归参数有：
  num：已经分割出多少个 ip 段；
  startIndex：截取 ip 段的起始位置；
  path：记录从根结点到叶子结点的一个路径
  temp:记录当前已经拼接得到的字符串

class Solution {
    public List<String> path = new ArrayList<>();
    //用于记录分割了几个整数，已经分割了四次才可能是有效IP
    public int num=0;
    public List<String> restoreIpAddresses(String s) {
        //剪枝
        if (s.length() < 4 || s.length() > 12) return path; 
        dfs(s,"",0);
        return path;
    }

    private void dfs(String s,String temp,int startIndex){
        //终止
        if(startIndex>=s.length()){
            //判断是否有效IP
            if(num==4) path.add(temp);
            return;
        }

        for(int i=startIndex;i<startIndex+3&&i<s.length();i++){
            //substring(startIndex,i+1)的取值范围是[startIndex,i]
            String str=s.substring(startIndex,i+1);
            if(isValidIP(str)){
                //分割数字+1
                num++;
                //最后一个IP不需要加"."
                if(num==4) dfs(s,temp+str,i+1);
                else dfs(s,temp+str+".",i+1);

                //回溯，但temp+str+"."不需要回溯
                num--;
            }else{
                //这条递归提前终止
                break;
            }
        }
    }

    private boolean isValidIP(String s){
        //以0开头但长度不为1，如023
        if(s.charAt(0)=='0'&&s.length()!=1) return false;
        //大小不在0-255之间
        int temp=Integer.valueOf(s);
        if(temp<0||temp>255) return false;
        return true;
    }
}