Given a string containing only digits, restore it by returning all possible valid IP address combinations.
    Example:
    Input: “25525511135”
    Output: ["255.255.11.135", "255.255.111.35"]
    这道题的难点在于：在进一步递归前，准备好当前已经获得的结果，并传入下一步的递归之中
    在递归出来后，恢复当前已经获得的结果，进入下一个递归路径

    1. public class Solution {
    3.     public List<String> restoreIpAddresses(String s) {
    4.     List<String> res  = new ArrayList();
    5.     if(s == null || s.length() == 0|| s.length()<4|| s.length()>12){
    6.         return res;
    7.     }
    9.     helper(res,s,new StringBuilder(), 0, 4);
    10.     return res;
    11. }
    13.     // pos 表示即将考察的字符的位置  初始值是 0
    14.     // left表示还需要几部分才能组成一个完整的ip  初始值是  4
    15.     private void helper(List<String> res, String s ,StringBuilder sb, int pos, int left){
    16.     if(pos == s.length() || left == 0){
    17.         // 当字符刚好用完，并且需要的ip的4部分都拼出来时，说明是一个可用的分割，加入结果集中。
    18.         if(pos == s.length() && left == 0){
    19.             res.add(sb.toString());
    20.         }
    21.         return;
    22.     }
    23.     // 在准备添加ip的第2、3、4部分时，先在临时结果中加入一个分隔的 . 号
    24.     if(left != 4){
    25.         sb.append(".");
    26.     }
    28.     int len = sb.length();
    29.     for(int i = pos + 1 ; i <= Math.min(pos+3,s.length());i++){
    30.         // 不考虑 123.04.34.11这种类型的ip， 04 不合法
    31.         if(i != pos+1 && s.charAt(pos) =='0'){
    32.             break;
    33.         } 
    34.         int num = Integer.parseInt(s.substring(pos,i));
    35.         if(num>=0 && num<=255){
    36.             sb.append(num);
    37.             helper(res,s,sb,i,left-1);
    38.            //将存储临时结果的sb进行复原，以便探索其他的路径
    39.             sb.setLength(len);
    40.         }
    41.     }
    42. }
    43. }