This program generates all possible permutations of a given string using recursion.

Program Structure

• Main Class: StringPermutations – This is the entry point of the program.
• Method: permute(String str, String current) – This recursive method generates permutations.
• Base Case: When the input string is empty, it prints the current permutation.
• Recursive Case: It loops through each character in the string, appending it to the current permutation and recursively calling itself with the remaining characters.

Java Code

import java.util.HashSet;

public class StringPermutations {
    
    public static void main(String[] args) {
        String str = "abc";
        System.out.println("All permutations of " + str + " are:");
        permute(str, "");
    }

    /**
     * Generates all permutations of the given string.
     *
     * @param str     The remaining string to permute.
     * @param current The current permutation being formed.
     */
    public static void permute(String str, String current) {
        if (str.length() == 0) {
            System.out.println(current);
        } else {
            HashSet seen = new HashSet<>(); // To avoid duplicates
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (!seen.contains(ch)) {
                    seen.add(ch); // Mark the character as seen
                    // Recursively permute the remaining string
                    permute(str.substring(0, i) + str.substring(i + 1), current + ch);
                }
            }
        }
    }
}
        

Explanation of the Code

The program starts with the main method, which initializes a string and calls the permute method.
The permute method works as follows:

1. If the remaining string str is empty, it prints the current permutation stored in current.
2. A HashSet named seen is used to avoid generating duplicate permutations when the string contains repeated characters.
3. The method loops through each character in the string. For each character:
   • If the character has not been seen before, it adds it to the seen set.
   • The method recursively calls itself with the remaining characters of the string and adds the current character to the current permutation.

Conclusion

This program effectively generates all permutations of a given string, ensuring that duplicate permutations are not produced.
By using recursion and a set to track seen characters, it efficiently explores all possible arrangements.