原题链接在这里：

题目：

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:

Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

题解：

Backtracking.

IP规则, 一共有四段. 每段数字在[0,255], 但当一段起始是0时, 它唯一的合法规则就是单独一个0. 

一共四段, dfs时用count计数现在是第几段. 到了第四段并且正好走到了s的末位, 把当前item加到res中.

Time Complexity: exponential. Space: O(1). 最多4层stack.

AC Java:

1 class Solution { 2     public List
     
       restoreIpAddresses(String s) { 3         List
      
        res = new ArrayList
       
        (); 4         if(s == null || s.length() < 4 || s.length() > 12){ 5             return res; 6         } 7  8         dfs(s, 0, 0, "", res); 9         return res;10     }11     12     private void dfs(String s, int start, int count, String item, List
        
          res){13         if(count > 4){14             return;15         }16         if(count == 4 && start == s.length()){17             res.add(item);18             return;19         }20         21         for(int i = 1; i<4&&start+i<=s.length(); i++){22             String sub = s.substring(start, start+i);23             if(isValid(sub)){24                 dfs(s, start+i, count+1, item+sub+(count==3 ? "" : "."), res);25             }26         }27     }28     29     private boolean isValid(String s){30         if(s.charAt(0) == '0'){31             return s.equals("0");32         }33         34         int num = Integer.valueOf(s);35         return num>0 && num<256;36     }37 }