String Permutations Recursion Java | Fresher Interview

Direct Answer

Use backtracking: for each position try placing each unused character, recurse to fill the remaining positions, then undo the choice. Track used characters with a boolean array. The base case is when the current length equals the original length. There are n! permutations, so time is O(n * n!).

Deep Dive & Architecture

A recursion level represents one position in the output. At that level, try every character that has not already been used, mark it, append it to the current path, and recurse for the next position. After the call returns, delete the character and clear its marker so another branch sees the original state.

Worked example: ABC

Choose A first. The next level can choose B, leaving C, which records ABC. Undo C and B, choose C second, then B, which records ACB. Backtrack to the root and repeat with B and C as the first choices. The six leaves are ABC, ACB, BAC, BCA, CAB, and CBA.

The base case is reached when the path length equals the input length. Store a copy or an immutable string at that point; storing the mutable builder itself would let later backtracking change earlier results.

There are n! complete outputs, and copying each length-n result makes the unavoidable running time O(n × n!). The path, used array, and recursion stack use O(n) working space, excluding the output. If input characters repeat, sort them and skip an equal unused choice at the same level to avoid duplicate permutations.

Code Example

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

public class PermutationGenerator {
    public static List<String> permute(String str) {
        List<String> result = new ArrayList<>();
        backtrack(str.toCharArray(), new StringBuilder(),
                  new boolean[str.length()], result);
        return result;
    }

    private static void backtrack(char[] chars, StringBuilder current,
                                  boolean[] used, List<String> result) {
        if (current.length() == chars.length) {   // base case: full permutation
            result.add(current.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (used[i]) continue;                 // skip used characters
            used[i] = true; current.append(chars[i]);          // choose
            backtrack(chars, current, used, result);           // explore
            current.deleteCharAt(current.length() - 1); used[i] = false; // un-choose
        }
    }
}

// permute("AB") -> [AB, BA]  (2! = 2 permutations)

Common Mistakes & Pitfalls

• Forgetting to backtrack: after recursing, not removing the last character and unmarking the used flag lets state leak into the next iteration and produces wrong results.
• Not understanding O(n!) complexity: saying it's O(n^n). The reason it's factorial is n choices for the first position, n-1 for the second, and so on.
• Confusing permutations and combinations: permutations care about order (ABC vs ACB differ); combinations don't. Make this distinction explicit.