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

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
johnny willer
Guest

Cool

David Leonhartsberger
Guest
David Leonhartsberger

Iterative solution does print 8 results and not 6. I recommend to test your code before you post it to the public.