# Write a method in Java that will find and print out all the possible combinations (or “permutations”) of the characters in a string. So, if the method is given the string “dog” as input, then it will print out the strings “god”, “gdo”, “odg”, “ogd”, “dgo”, and “dog” – since these are all of the possible permutations of the string “dog”. Even if a string has characters repeated, each character should be treated as a distinct character – so if the string “xxx” is input then your method will just print out “xxx” 6 times.

Finding an algorithm to answer this question may seem challenging because finding all the different permutations of a string is something that you just do naturally without really thinking about it. But, try to figure out what algorithm you are implicitly using in your mind whenever you write down all the different permutations of a string. Let’s use the word “dogs” as an example and see what different permutations we get. Here is what comes up when we list out all the possible permutations of the letters in “dogs”:

dogs sgod gsod ogsd dosg sgdo gsdo ogds dsgo sdgo gdso osdg dsog sdog gdos osgd dgso sodg gods odgs dgos sogd gosd odsg

So, when we came up with the permutations of “dogs” above, how did we do it? What were we implicitly thinking? Well, it looks like what we did in each column was choose one letter to start with, and then we found all the possible combinations for the string beginning with that letter. And once we picked a letter in the 2nd position, we then found all the possible combinations that begin with that 2 letter sequence before we changed any of the letters in the first 2 positions. So, basically what we did was choose a letter and then peformed the permutation process starting at the next position to the right before we come back and change the character on the left.

## Finding the permutations with recursion

Our description of the process that we followed sounds a lot like something that could be solved with recursion. How can we change our description so that it’s easier to write out in a recursive method? Let’s phrase it like this: In order to find all possible combinations for a given string, then start at a position x, then find and place all possible letters in position x. Every time we put a new letter in position x, we should then find all the possible combinations at position x+1 – this would be the recursive call that we make. How do we know when to print out a string? Well, when we are at a position x that is greater than the number of letters in the input string, then we know that we have found one valid combination/permutation of the string and then we can print it out and return to changing letters at positions less than x. This would be our base case – remember that we always must have a recursive case and a base case when using recursion.

## Which letters can we use in a given position?

Another big part of this problem is figuring out which letters we can put in a given position. Using our sample string “dogs”, lets say that we are going through all the permutations where the first 2 letters are “gs”. Then, it should be clear that the letters in the 3rd or 4th position can only be either “d” or “o”, because “g” and “s” were already used. As part of our algorithm, we have to know which letters can be used in a given position – because we can’t *reuse* the letters that were used in the earlier positions. And in order to do this we can simply have an array of Boolean values that correspond to the positions of the letters in the input string – so if a certain character from the input string has already been used, then it’s position in the array would be set to “true”.

## Find all the permutations of a string in Java

Now, here is what the Java method would like for our algorithm:

void permute( String input) { int inputLength = input.length(); boolean[ ] used = new boolean[ inputLength ]; StringBuffer outputString = new StringBuffer(); char[ ] in = input.toCharArray( ); doPermute ( in, outputString, used, inputLength, 0 ); } void doPermute ( char[ ] in, StringBuffer outputString, boolean[ ] used, int inputlength, int level) { if( level == inputLength) { System.out.println ( outputString.toString()); return; } for( int i = 0; i < inputLength; ++i ) { if( used[i] ) continue; outputString.append( in[i] ); used[i] = true; doPermute( in, outputString, used, length, level + 1 ); used[i] = false; outputString.setLength( outputString.length() - 1 ); } }

If you are wondering why we used StringBuffer instead of String in the code above - you can read more about that here: String vs StringBuffer.