private static ArrayList<String> subIP (String str, int n) {
    	ArrayList<String> ret = new ArrayList<String>();
    	if (str.length() == 0 || str.length() > n * 3) {
    		return ret;
    	}
    	else {
    		for (int i = Math.min(3, str.length()); i > 0; --i) {
    			String first_num = str.substring(0, i);
    			if (isValid(first_num) && str.length()-i <= 3 * (n-1)) {
    				
    				//check the rest
    				if (n-1 == 0) {
    					ret.add(first_num);
    				}
    				else {
	    				ArrayList<String> sub_ret = subIP(str.substring(i), n-1);
	    				if (sub_ret.size() != 0) {//valid return
	    					//System.out.println(sub_ret.size() + "n" + n);
	    					for (int j = 0; j < sub_ret.size(); ++j) {
	    						String temp = first_num + "." + sub_ret.get(j);
	    						ret.add(temp);
	    					}
	    				}
    				}
    			}
    		}
    	}
    	return ret;
    }