题目：

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)

思路：递归，回溯

c++代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;class Solution {public:    vector
         
           restoreIpAddresses(string s) {        vector
          
            v; string t = ""; dfs(s, t, v, 1); return v; } void dfs(string s, string t, vector
           
             &v, int count){ if(count == 4){ if(isValid(s)){ v.push_back(t+s); } return; } int i; for(i = 1; i < 4; i++){ if(i < s.size()){ string g = s.substr(0, i); if(isValid(g)){ string m = s.substr(i); dfs(m, t + g + ".", v, count + 1); } } } } bool isValid(string g){ int l = g.size(); if(l > 3)return false; if( l >=2 && g[0] == '0')return false; int vv = atoi(g.c_str()); return vv <= 255 && vv >= 0; }};int main(){ Solution *s = new Solution(); vector
            
              r = s->restoreIpAddresses("1111"); vector
             
              ::iterator iter; for(iter = r.begin(); iter != r.end(); iter++){ cout << *iter << endl; } delete s; return 1;}