class Solution {
    private void backtracking(String s,int index,String t,int k, List<String> res){
        if(index==s.length()&&k==4){
            res.add(t.substring(0,t.length()-1));
            return;
        }
        if(k>4)
            return;
        int d=0;
        for(int i=index;i<s.length();i++){
            d=d*10+s.charAt(i)-'0';
            if(d>255)
                return;
            backtracking(s,i+1,t+d+'.',k+1,res);
            if(d==0)
                return;
        }
    }
    public List<String> restoreIpAddresses(String s) {
        List<String> res=new ArrayList<>();
        backtracking(s, 0, "",0, res);
        for(String s1: res){
            System.out.println(s1);
        }
        return res;
    }

    public static void main(String[] args) {
        new Solution().restoreIpAddresses("25525500");
    }
}