public class Solution {

    public List<String> restoreIpAddresses(String s) {

        List<String> res = new ArrayList<String>();

        int len = s.length();

        for(int i = 1; i<4 && i<len-2; i++){

            for(int j = i+1; j<i+4 && j<len-1; j++){

                for(int k = j+1; k<j+4 && k<len; k++){

                    String s1 = s.substring(0,i), s2 = s.substring(i,j), s3 = s.substring(j,k), s4 = s.substring(k,len);

                    if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){

                        res.add(s1+"."+s2+"."+s3+"."+s4);

                    }

                }

            }

        }

        return res;

    }

    public boolean isValid(String s){

        if(s.length()>3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s)>255)

            return false;

        return true;

    }

}　　

public List<String> restoreIpAddresses(String s) {

    List<String> solutions = new ArrayList<String>();

    restoreIp(s, solutions, 0, "", 0);

    return solutions;

}

private void restoreIp(String ip, List<String> solutions, int idx, String restored, int count) {

    if (count > 4) return;

    if (count == 4 && idx == ip.length()) solutions.add(restored);

    for (int i=1; i<4; i++) {

        if (idx+i > ip.length()) break;

        String s = ip.substring(idx,idx+i);

        if ((s.startsWith("0") && s.length()>1) || (i==3 && Integer.parseInt(s) >= 256)) continue;

        restoreIp(ip, solutions, idx+i, restored+s+(count==3?"" : "."), count+1);

    }

}　　

public class Solution {

    public List<String> restoreIpAddresses(String s) {

        List<String> res = new ArrayList<String>();

        for (int a = 1; a < 4; ++a)

        for (int b = 1; b < 4; ++b)

        for (int c = 1; c < 4; ++c)

        for (int d = 1; d < 4; ++d)

            if (a + b + c + d == s.length()) {

                int A = Integer.parseInt(s.substring(0, a));

                int B = Integer.parseInt(s.substring(a, a + b));

                int C = Integer.parseInt(s.substring(a + b, a + b + c));

                int D = Integer.parseInt(s.substring(a + b + c));

                if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {

                    String t = String.valueOf(A) + "." + String.valueOf(B) + "." + String.valueOf(C) + "." + String.valueOf(D);

                    if (t.length() == s.length() + 3) res.add(t);

                }

            }

        return res;

    }

}

public class Solution {

    public List<String> restoreIpAddresses(String s) {

        List<String> res = new ArrayList<String>();

        helper(s, 0, "", res);

        return res;

    }

    public void helper(String s, int n, String out, List<String> res) {

        if (n == 4) {

            if (s.isEmpty()) res.add(out);

            return;

        }

        for (int k = 1; k < 4; ++k) {

            if (s.length() < k) break;

            int val = Integer.parseInt(s.substring(0, k));

            if (val > 255 || k != String.valueOf(val).length()) continue;

            helper(s.substring(k), n + 1, out + s.substring(0, k) + (n == 3 ? "" : "."), res);

        }

    }

}

class Solution:

    # @param s, a string

    # @return a list of strings

    def restoreIpAddresses(self, s):

        result = []

        self.restoreIpAddressesRecur(result, s, 0, "", 0)

        return result

    def restoreIpAddressesRecur(self, result, s, start, current, dots):

        # pruning to improve performance

        if (4 - dots) * 3 < len(s) - start or (4 - dots) > len(s) - start:

            return

        if start == len(s) and dots == 4:

            result.append(current[:-1])

        else:

            for i in xrange(start, start + 3):

                if len(s) > i and self.isValid(s[start:i + 1]):

                    current += s[start:i + 1] + '.'

                    self.restoreIpAddressesRecur(result, s, i + 1, current, dots + 1)

                    current = current[:-(i - start + 2)]

    def isValid(self, s):

        if len(s) == 0 or (s[0] == '0' and s != "0"):

            return False

        return int(s) < 256

vector<string> restoreIpAddresses(string s) {

        vector<string> ret;

        string ans;

        for (int a=1; a<=3; a++)

        for (int b=1; b<=3; b++)

        for (int c=1; c<=3; c++)

        for (int d=1; d<=3; d++)

            if (a+b+c+d == s.length()) {

                int A = stoi(s.substr(0, a));

                int B = stoi(s.substr(a, b));

                int C = stoi(s.substr(a+b, c));

                int D = stoi(s.substr(a+b+c, d));

                if (A<=255 && B<=255 && C<=255 && D<=255)

                    if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3)

                        ret.push_back(ans);

            }    

        return ret;

    }