# Java Program to find all the permutations of a string

To solve this problem, we need to understand the concept of backtracking.

According to the backtracking algorithm:

• 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.

For programming, follow the algorithm given below:

### Algorithm

main()

• STEP 1: START
• STEP 2: DEFINE string str = “ABC”.
• STEP 3: len = str.length().
• STEP 4: PRINT “All the permutations of the string are:”
• STEP 5:CALL generatePermutation(str, 0, len).
• STEP 6: END

generatePermutation(String str, int start, int end)

• STEP 1: START
• STEP 2: if(start==end-1)
PRINT str
else go to STEP 3
• STEP 3: SET i = start. REPEAT STEP 4 to STEP 7 UNTIL i<end.
• STEP 4: str = swapstring(str, start, i).
• STEP 5: generatePermutation(str, start + 1, end).
• STEP 6: str = swapstring(str, start, i).
• STEP 7: i=i+1
• STEP 8: END

swapString(String a, int i, int j)

• STEP 1: START
• STEP 2: char[] b = a.toCharArray()
• STEP 3: DEFINE char ch
• STEP 4: ch =b[i]
• STEP 5: b[i] = b[j]
• STEP 6: b[j] = ch
• STEP 7: RETURN String.ValueOf(b)
• STEP 8: END

### Program:

1. public class PermuteString {
2.     //Function for swapping the characters at position I with character at position j
3.     public static String swapString(String a, int i, int j) {
4.         char[] b =a.toCharArray();
5.         char ch;
6.         ch = b[i];
7.         b[i] = b[j];
8.         b[j] = ch;
9.         return String.valueOf(b);
10.     }
11.
12.     public static void main(String[] args)
13.     {
14.         String str = “ABC”;
15.         int len = str.length();
16.         System.out.println(“All the permutations of the string are: “);
17.         generatePermutation(str, 0, len);
18.     }
19.
20.     //Function for generating different permutations of the string
21.     public static void generatePermutation(String str, int start, int end)
22.     {
23.         //Prints the permutations
24.         if (start == end-1)
25.             System.out.println(str);
26.         else
27.         {
28.             for (int i = start; i < end; i++)
29.             {
30.                 //Swapping the string by fixing a character
31.                 str = swapString(str,start,i);
32.                 //Recursively calling function generatePermutation() for rest of the characters
33.                 generatePermutation(str,start+1,end);
34.                 //Backtracking and swapping the characters again.
35.                 str = swapString(str,start,i);
36.             }
37.         }
38.     }
39. }

Output:

```All the permutations of the string are:
ABC
ACB
BAC
BCA
CBA
CAB```