We will use a very simple approach to do it.

Take out first character of String and insert into different places of permutations of remaining String recursively.

Lets say you have String as **ABC**.

So we take out A from ABC

**First character =A and RemainingString = BC **

As we are applying recursion here, we will find permutations of BC.

Take out B from BC.

**First character= B and RemainingString = C **

As we are applying recursion here, we will find permutations of C.

When we take out C, our String size becomes 0 and that is our base case here.

**First character**** = C and RemainingString = “” **

We insert C to differences indexes of Permutations of RemainingString(“”), so we get permutation of C as C.

We insert B to different indexes of Permutations of remainingString(C), so we get BC and CB.

**C: BC, CB**

Now we insert A to different indexes in BC and CB.

**BC : ABC , BAC , BCA**

**CB : ACB, CAB, CBA**

so thats how we got all permutations of ABC.

It may look tricky but once you practice the solution, you will be able to understand it better.

### Java program to find all Permutations of String in java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
package org.arpit.java2blog; import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class PermutationOfStringJava { public static void main(String[] args) { Set set=permutationOfString("ABC"); System.out.println("Permutations of String ABC are:"); for (Iterator iterator = set.iterator(); iterator.hasNext();) { String string = (String) iterator.next(); System.out.println(string); } } public static Set permutationOfString(String str) { Set permutationSet=new HashSet(); if(str.length()==0) { permutationSet.add(""); return permutationSet; } // take out first character of String char c=str.charAt(0); // Remaining String String rem=str.substring(1); Set permutatedSetForRemainingString=permutationOfString(rem); for (String permutedString: permutatedSetForRemainingString) { for (int j = 0; j <= permutedString.length(); j++) { String permutation=insertFirstCharAtDiffPlaces(permutedString,c,j); permutationSet.add(permutation); } } return permutationSet; } public static String insertFirstCharAtDiffPlaces(String perm,char firstChar,int index) { // Inserting firstCharacter of orig String at difference places based on index return perm.substring(0,index)+firstChar+perm.substring(index); } } |

1 2 3 4 5 6 7 8 9 |
Permutations of String ABC are: ACB ABC BCA CBA CAB BAC |