class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        restore(s, 4, "", result);
        return result;
    }
    
private:
    void restore(string s, int k, string path, vector<string> &result)
    {
        if(k == 0)
        {
            if(s.empty())
                result.push_back(path);
        }
        else
        {
            for(int i=1; i<=3; ++i)
            {
                if(s.size() >= i && isValid(s.substr(0, i)))
                {
                    if(k == 1)
                        restore(s.substr(i), k-1, path + s.substr(0, i), result);
                    else
                        restore(s.substr(i), k-1, path + s.substr(0, i) + ".", result);
                }
            }
        }
    }
    
    bool isValid(string s)
    {
        if(s.size() > 3 || s.empty() || (s.size() > 1 && s[0] == ‘0‘))
            return false;
            
        int num = stoi(s);
        return num >= 0 && num <= 255;
    }
};