public class  {
    List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(s, "", 0, 0);
        return res;
    }
    
    
    // cur用来存当前的字符串，以点号为结尾
    // index 为当前走到字符串s的位置。
    private void dfs(String s, String cur, int index,int count) {
        
        if(index == s.length() && count == 4){
            // 去掉最后的点号
            res.add(cur.substring(0, cur.length()-1));
        }
        
        if(count > 4 || index== s.length()  ) {
            return;
        }
        
        if(s.charAt(index) == '0') {
            // 不能有leading zero
            dfs(s, cur+"0"+".", ++index,count+1);
        } else {
            // 回溯的主体
            String num = s.charAt(index) + "";
            while(index<s.length() && Integer.parseInt(num) <= 255) {
                // 小于等于 255 的数字都可以作为下一个部分
                dfs(s, cur+num+".", ++index, count+1);
                
                // 越界则退出
                if(index==s.length()){
                    break;
                }
                // 继续给 num 添加一位
                num = num+s.charAt(index);
            }
        }
    }
}