How to Find All Permutations of String in Java using Recursion

How to find all permutation of a String using recursion is one of the tricky coding question from Programming job interviews. I have first seen this question in my college exam, when we were asked to code the solution using C or C++ language. Since then I have seen this question many times at various written tests and Java interviews for junior developer position. Its not only serve as a good question to check whether candidate understand recursion but also its one of the better Java programming exercise for beginners. Typically, you will be asked to write a method, which accepts a String and print all permutations or may be return all permutations in a List. Depending upon the company you are going for interview, they may ask you to code on IDE like Eclipse or NetBeans, or simply write code in plain paper, so be prepared for both. There are two main ways to solve this problem, using loops or by using recursion, second one is what interviewer expect. Since recursion is a tricky programming concept to master, it's not easy for every programmer to solve this problem on the fly, especially if you are not coding on daily basis or don't have that highly sought after code sense. Like everything else, practice is your friend, doing this kind of coding exercises on daily basis, solving programming puzzles and doing more complex programs available on internet sites like project Euler, TopCoder will help you to build confidence in your coding and problem solving skill. You can also take help of some classic books like Programming Interviews Exposed and Cracking the Coding Interview books to do well on coding interviews

Solution  - Using Recursion and Loop

Now let's get back to the problem, Permutation refers to ordering of characters but it takes position in to account i.e. if you have String "ab" then it will have just 2 permutations "ab" and "ba", because position of character in both String are different. Similarly for a String of n characters there are !n (factorial of n) permutations are possible e.g. for a String of 3 characters like "xyz" has 6 possible permutations, xyz, xzy, yxz, yzx, zxy, zyx as seen in our example. As I told there are two ways to solve this problem either by using for loop (iterative algorithm) or by using recursion, but most elegant solution is combination of both loop and recursion.

If you remember the factorial problem you know that factorial is naturally recursive i.e. factorial of n is nothing but n * factorial of n -1. Similarly, permutations are also recursive e.g. permutation of n characters is nothing but fixing one character and calculating permutation of n - 1 characters e.g. in case of "xyz", you can fix "x" and calculate permutation of "yz". In order to calculate all permutation of a String you need to repeat this exercise for all characters one at a time. This is where for loop comes into picture. So, this solution uses both for loop and recursion to print all permutation of given String.

In case of recursion, the most important question is base case, because that is responsible for stopping recursive call. If you don't have base case then your program will eventually terminate with java.lang.StackOverFlowError. In this problem, our base case is permutation of empty String, which is nothing but the empty String itself. After each call, problem set is reduced and inches towards base case, when it reaches there stack starts rolling down and calculates result.

Java Program to Print All Permutation of a String

Here is our sample Java program to print all permutations of given String using recursive algorithm. It uses both loop and recursive call to solve this problem. It also demonstrate a technique of hiding your implementation detail using a private method and exposing a much cleaner public method as API. In our solution, we have two permutation method, one is public and other is private. First method is clean and exposed to client but second method require you to pass an empty String as initial value of perm parameter which is used to store intermediate permutation of String. If you expose this method to client then it will wonder about this empty String, since its part of implementation, its better to hide and get rid of it as soon as you have a better algorithm to solve this problem, how about taking it as an exercise?

/**
  * Java program to find all permutations of a given String using recursion. 
  * For example, given a String "XYZ", this program will print all 6 possible permutations of
  * input e.g. XYZ, XZY, YXZ, YZX, ZXY, XYX
  *
  * @author Javin Paul
  */
public class StringPermutations {

    public static void main(String args[]) {
        permutation("123");
    }

   
 /*
  * A method exposed to client to calculate permutation of String in Java. 
  */
   public static void permutation(String input){
          permutation("", input);
   }

   /*
    * Recursive method which actually prints all permutations
    * of given String, but since we are passing an empty String
    * as current permutation to start with,
    * I have made this method private and didn't exposed it to client. 
    */
   private static void permutation(String perm, String word) {
        if (word.isEmpty()) {
            System.err.println(perm + word);

        } else {
            for (int i = 0; i < word.length(); i++) {
                permutation(perm + word.charAt(i), word.substring(0, i) 
                                        + word.substring(i + 1, word.length()));
            }
        }

    }
}

Output:
123
132
213
231
312
321

Explanation of Code :

All code for calculating permutation of String is inside permutation(String perm, String word)  method, I have purposefully made this method private because of additional parameter I am passing as initial value of permutation. This demonstrate a technique of hiding implementation detail from client and exposing much cleaner API to client e.g. just permutation(String input)  method, passing empty String is implementation detail and ugly for client to pass whenever it needs to calculate permutation. It is also an exercise for you to see if you can improve the code by getting rid of that empty String.

Algorithm is nothing but keeping one character fix and then calculating permutations of others. Crux of program is in following code segment :

 for (int i = 0; i < word.length(); i++) {
   permutation(perm + word.charAt(i), word.substring(0, i) 
                    + word.substring(i + 1, word.length()));
}

Here we have a for loop to go through each character of String e.g. for input "123" this loop will run three times. In each iteration we are making recursive call to function itself  i.e. permutation(String perm, String word)  method, where first parameter is used to store result.


After 1st iteration perm (first parameter of permutation() method) will be "" + 1 as we are doing word.charAt(i) and i is zero. Next, we take out that character and pass the remaining characters to permutation method again e.g. "23" in first iteration. Recursive call ends when it reaches to base case i.e. when remaining word becomes empty, at that point "perm" parameter contains a valid permutation to be printed. You can also store it into a List if you wants to.

Here is a nice diagram which visually shows what this algorithm does :

That's all on how to find all permutations of a String in Java using recursion. It's a very good exercise for preparing Java coding interviews. Why not you give it a try and come up with another solution? also could you calculate complexity of this algorithm, to me it looks n*!n because loop will run for n times and for each n, we will call permutation method. Also, how about writing some JUnit test cases to see if this solution works for various input e.g. empty String, one letter String, many letters String, String with duplicate characters etc? It's a good practice to become hands on writing JUnit tests.


If you are interested for more of such coding question, you can check following interview questions collected from various Java interviews :

• 20 String based Coding Problems from Java Interviews [solution]
• 30 Array based Coding Questions from Java Interviews [solution]
• How to check if two String are anagram of each other? [solution]
• How to find duplicate words in a given String? [solution]
• How to check if given String is Palindrome in Java? [solution]
• How to print first non repeated character from given String in Java? [solution]
• How to reverse String in Java without using recursion? [solution]
• How to count occurrence of a given character in String? [solution]