Generate All Permutations of a String

📌 Definition:

📖 Detailed Explanation:

Use backtracking/recursion: fix each character at the current position and recurse on the rest, swapping back after each choice. There are n! permutations, so the time is O(n * n!). Deduplicate if the input has repeated characters.

💻 Solutions:

• Java
• JavaScript
• Python

public static List<String> permutations(String s) {
    List<String> out = new ArrayList<>();
    permute(s.toCharArray(), 0, out);
    return out;
}
private static void permute(char[] a, int k, List<String> out) {
    if (k == a.length) { out.add(new String(a)); return; }
    for (int i = k; i < a.length; i++) {
        char t = a[k]; a[k] = a[i]; a[i] = t;   // swap
        permute(a, k + 1, out);
        t = a[k]; a[k] = a[i]; a[i] = t;         // undo
    }
}

function permutations(s) {
  const out = [];
  const a = s.split('');
  (function permute(k) {
    if (k === a.length) { out.push(a.join('')); return; }
    for (let i = k; i < a.length; i++) {
      [a[k], a[i]] = [a[i], a[k]];
      permute(k + 1);
      [a[k], a[i]] = [a[i], a[k]];
    }
  })(0);
  return out;
}

from itertools import permutations as perm

def permutations(s):
    return [''.join(p) for p in perm(s)]

🔑 Key Points:

• Backtracking: choose, recurse, undo
• n! permutations -> O(n * n!) time
• Use a set or skip duplicates for repeated chars
• Base case: index reaches the end

🌍 Real-World Example: