Generate all Permutations of a String in Java | Recursive & Iterative

Write a Java program to generate all permutations of a string.


 

1. Recursive Approach

Since String is immutable in Java, the idea is to convert the string to character array. Then we can inplace generate all permutations of a given string by using Backtracking by swapping each of the remaining characters in the string with its first character and then generate all the permutations of the remaining characters using a recursive call.

Below is the recursion tree for printing all permutations of string “ABC”.

Generate all permutations of a string

 

Download   Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

 
Here’s another Java implementation that doesn’t convert the String to charater array.

 

Download   Run Code

Output:

ABC
ACB
BAC
BCA
CAB
CBA

 

2. Iterative Approach: (Using Collection) –

 
Below implementation uses ArrayList to store the partially generated permutations and then use those partial permutations to generate the final permutations in further iterations.

 

Download   Run Code

Output:

[CAB, ACB, ABC, CBA, BCA, BAC]

 
Author: Lucas Daniel

 
Also see: Find all Lexicographic Permutations of a String

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz