void getWays(const string &A, set<string> &s, int start = 0, int part = 0, string output= "") {
if(part == 4) {
if(start == A.size()) {
output.pop_back();
s.insert(output);
}
return;
}
for(int end = start; end < min(start + 3, (int)A.size()); end++) {
string sub = A.substr(start, end - start + 1);
if(stoi(sub) < 256 && (start == end || sub[0] != '0'))
getWays(A, s, end + 1, part + 1, output + sub + ".");
}
}
vector<string> Solution::restoreIpAddresses(string A) {
vector<string> res;
if(A.size() > 12)
return res;
set<string> s;
getWays(A, s);
for(auto x: s)
res.push_back(x);
return res;
}