思路：递归+回溯+剪枝（valid判断）
class Solution {
public:
vector<string> restoreIpAddresses(string s) {

    vector<string> res;
    if(s.length()<4)
        return res;
    
    backtracking(0,"",res,s,1);

    return res;
}

void backtracking(int begin,string tmp, vector<string>& res, string s,int index)
{
    if(index==5)
    {
        if(begin==s.length())
        {
            res.push_back(tmp);
        }
        return;
    }

    for(int i=begin;i<begin+3 && i<s.length();i++)
    {
        
        string r=s.substr(begin,i-begin+1);

        if(valid(r))
        {
            if(index<4)
            r=r+'.';
            backtracking(i+1,tmp+r,res,s,index+1);
        }
    
        continue;
    }

}

bool valid(string s)
{
    if(s.length()>1 && s[0]=='0')
        return false;
    
    if(stoi(s)>255)
        return false;

    return true;

}

};