DFS+回溯

将字符串划分成ip地址，需要注意几点：
1、ip地址由四个整数组成；
2、每个整数的范围是[0,255]；
3、四个整数通过逗号分隔符连接
4、每个整数除了它本身是0的情况之外，不能以0开头
我主要采用深度优先搜索+回溯的方法解决

对每一部分的整数的处理方式都是一样的，先取一位数，然后添加到临时要划分的ip字符串中，继续递归进行后面整数的划分，递归的过程中，如果划分出四个整数同时字符串又使用完毕，则组成了一种ip，否则就不是，直接返回。

    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        if (s == null || s.length() <= 3 || s.length() > 12){
            return new ArrayList<>();
        }
        ArrayList<String> list = new ArrayList<>();
        backTrace(0,s,list,new StringBuilder());

        return list;
    }


    private void backTrace(int partNum, String s, List<String> list,StringBuilder midIp){

        if (partNum == 4 || s.length() == 0){

            if (partNum == 4 && s.length() == 0){
                list.add(midIp.toString());

            }
            return;
        }

        for (int i = 0; i <= 2 && i < s.length(); i++) {

            if (i != 0 && s.charAt(0) == '0'){
                break;
            }

            String substring = s.substring(0, i + 1);

            if (Integer.valueOf(substring) <= 255){

                if (midIp.length() != 0){
                    substring = "." + substring;
                }

                midIp.append(substring);
                backTrace(partNum+1,s.substring(i+1),list,midIp);
                midIp.delete(midIp.length() - substring.length(),midIp.length());
            }
        }

    }