/*

Backtracking algorithm used in the program:-

>>Fix a character in the first position and swap the rest of the character with the first character.

Like in ABC, in the first iteration three strings are formed: ABC, BAC, and CBA by swapping A with

A, B and C respectively.

>>Repeat step 1 for the rest of the characters like fixing second character B and so on.

>>Now swap again to go back to the previous position. E.g., from ABC, we formed ABC by fixing B again,

and we backtrack to the previous position and swap B with C. So, now we got ABC and ACB.

>>Repeat these steps for BAC and CBA, to get all the permutations.

*/

public class PermuteString {

//Function for swapping the characters at position I with character at position j

public static String swapString(String a, int i, int j) {

char[] b =a.toCharArray();

char ch;

ch = b[i];

b[i] = b[j];

b[j] = ch;

return String.valueOf(b);

}

public static void main(String[] args)

{

String str = "ABC";

int len = str.length();

System.out.println("All the permutations of the string are: ");

generatePermutation(str, 0, len);

}

//Function for generating different permutations of the string

public static void generatePermutation(String str, int start, int end)

{

//Prints the permutations

if (start == end-1)

System.out.println(str);

else

{

for (int i = start; i < end; i++)

{

//Swapping the string by fixing a character

str = swapString(str,start,i);

//Recursively calling function generatePermutation() for rest of the characters

generatePermutation(str,start+1,end);

//Backtracking and swapping the characters again.

str = swapString(str,start,i);

}

}

}

}