Generate All Permutations of a String

Given a string S of N distinct uppercase English letters, generate all N! permutations of its characters using recursion: fix each unused character in turn at the current position, recurse on the remaining positions, then backtrack. Print every permutation in the order the recursion produces them when, at each step, characters are tried in the same left-to-right order they appear in S, one permutation per line.

Input: A single line containing the string S of N distinct uppercase letters. Output: N! lines, each containing one permutation of S, in the order generated by the recursion described above.

1 <= N <= 8. All characters of S are distinct uppercase English letters.

The specific requirement that characters be tried 'in the order they appear in S' at every level is what fixes the EXACT output order shown - a different trying order would still generate all N! permutations, just not in this specific sequence.

Generate every possible reordering of a string's characters using recursive backtracking. Brute force: There isn't really a 'slower' alternative here - generating all N! permutations genuinely requires visiting each one, and the recursive backtracking IS the direct, standard way to do so. Optimised: The 'used' array lets each recursive call efficiently check which characters remain available in O(1) per candidate, and the mark-used/recurse/mark-unused (backtrack) pattern ensures every permutation is generated EXACTLY once, with no duplicates and no missed arrangements.

1. Maintain a boolean 'used' array tracking which characters are already placed in the CURRENT permutation being built. 2. At each position, try every UNUSED character in the order it appears in S, recurse into the next position, then BACKTRACK (mark it unused again) before trying the next candidate. 3. The BASE CASE is when the current permutation reaches length N - print it.

Time: O(N! * N) - there are N! permutations, and each takes O(N) to construct and print. Space: O(N) for the recursion stack and the 'used' array, plus O(N! * N) if all permutations are collected before printing.

N = 1 produces exactly one line, S itself. N = 8 produces 40320 permutations and is the largest input this problem is tested with.

Be ready to explain the BACKTRACKING step explicitly (marking a character unused again after its recursive branch returns) - forgetting this step is the most common bug, since it would cause characters to remain permanently 'used' across sibling branches.