Java Recursive Method: Generate all possible permutations

Java Recursive: Exercise-11 with Solution

Write a Java recursive method to generate all possible permutations of a given string.

Sample Solution:

Java Code:

import java.util.ArrayList;
import java.util.List;

public class StringPermutationGenerator {

  public static List < String > generatePermutations(String str) {
    List < String > permutations = new ArrayList < > ();
    generatePermutationsHelper(str, "", permutations);
    return permutations;
  }

  private static void generatePermutationsHelper(String str, String current, List < String > permutations) {
    // Base case: if the string is empty, add the current permutation to the list
    if (str.isEmpty()) {
      permutations.add(current);
      return;
    }

    // Recursive case: for each character in the string, generate permutations by
    // appending the character to the current permutation, and recursively call the method
    // with the remaining characters as the new string
    for (int i = 0; i < str.length(); i++) {
      char ch = str.charAt(i);
      String remaining = str.substring(0, i) + str.substring(i + 1);
      generatePermutationsHelper(remaining, current + ch, permutations);
    }
  }

  public static void main(String[] args) {
    String input = "abc";
    List < String > permutations = generatePermutations(input);
    System.out.println("Permutations of \"" + input + "\":");
    for (String permutation: permutations) {
      System.out.println(permutation);
    }
  }
}

Sample Output:

Permutations of "abc":
abc
acb
bac
bca
cab
cba

Explanation:

In the above exercises -

First, we define a class "StringPermutationGenerator" that includes a recursive method generatePermutations() to generate all possible permutations of a given string str.

The generatePermutations() method has two cases:

• Base case: If the string is empty (str.isEmpty()), we add the current permutation (current) to the list of permutations.
• Recursive case: For any non-empty string, we iterate through each character in the string and generate permutations by appending the character to the current permutation. We then recursively call the method with the remaining characters as the new string. This process continues until the string is reduced to an empty string.

In the main() method, we demonstrate the generatePermutations() method by generating all possible permutations of the string "abc" and printing the result.

Flowchart:

Java Code Editor:

Java Recursive Previous: Find the length of a string.
Java Recursive Next: Find the maximum element.