## How to generate all the valid IP Addresses from a String of number

Generating the valid IP addresses from a String is a classic interview question. It is done using back tracking and a utility method that test is the current subString is a valid digit.

The main method loops on the characters of the input String. If the subString is a valid character, it remembers it and calls itself searching for n-1 characters. If at any point no characters are available or the sub String is not a valid digit, then the process stops.

### Create the following java file:

```import java.util.ArrayList;
import java.util.List;

public class InterviewValidIP {

ArrayList<String> toReturn = new ArrayList<String>();
if( A == null )

process(toReturn, "", A, 4);

}

public void process(ArrayList<String> toReturn, String tmpIP,
String in, int remaining){

if( remaining == 0 && in.length() == 0 ) {
return;
}

for( int i = 1 ; i <= in.length() ; i++ ){
String tmp = in.substring(0, i);

if( !isValidDigit(tmp) ){
return;
}

StringBuilder updatedIP = new StringBuilder();
updatedIP.append( tmpIP );
if ( tmpIP.length() != 0 )
updatedIP.append( "." );

updatedIP.append( tmp );

String remainder = in.substring( i, in.length() );

int lessOne = remaining - 1;
process( toReturn, updatedIP.toString(), remainder, lessOne);
}
}

public boolean isValidDigit(String in){
int i = -1;
try { i = Integer.parseInt( in ); }catch(Exception e){}

if( i == -1  )
return false;
if( i != 0 && in.charAt(0) == '0' )
return false;

if( i == 0 && in.charAt(0) == '0' && in.length() != 1 )
return false;

return i >= 0 && i <= 255;
}

public static void main(String[] argv) throws Exception {
InterviewValidIP t = new InterviewValidIP();

List<String> out = t.restoreIpAddresses( "0100100" );

for(String c : out){
System.out.println( "found=" + c );
}
}

}

```

### The output will be:

```found=0.10.0.100
found=0.100.10.0

```

The utility method is called isValidDigit, it validate that the number is a valid integer that is positive and less that 256. It also check that the number doesn't start with 0 if it's not 0.