Permutation Generation Using Recursion

This problem requires you to generate all possible permutations of a given string using a recursive algorithm. Given a string \(s\), your task is to compute all unique orderings (permutations) of its characters. The solution should use recursion and, for consistency, the output permutations must be sorted in lexicographical order.

Note: Even if the input string is empty, consider it as a valid case (output should be a single empty string). The output for non-empty strings should list each permutation on a separate line.

inputFormat

The input consists of a single line containing a string \(s\). The string may contain one or more characters. Note that the string will not be empty in the test cases provided.

outputFormat

Output all the permutations of the given string, one permutation per line. The order of the permutations must be sorted in lexicographical order.

a

a