本文详解如何用 stringbuilder 高效实现字符串全排列，避免字符串拼接开销，并修正递归回溯中常见的状态重置错误，确保输出完整、无重复、无越界异常。
在 Java 中，使用 String 实现全排列虽直观，但因 String 不可变，每次拼接都会创建新对象，时间与空间开销较大。而 StringBuilder 是可变的、线程不安全但高性能的字符序列容器，更适合递归回溯类操作——前提是必须精准管理其状态：进入递归前修改，返回后彻底还原。
下面是一个正确、健壮、可直接运行的 StringBuilder 版全排列实现：
public class PermutationWithStringBuilder {
public static void permutations(StringBuilder str, StringBuilder ans) {
// 递归终止条件：原字符串已选尽
if (str.length() == 0) {
System.out.println(ans);
return;
}
// 遍历当前可选的所有字符位置
for (int i = 0; i < str.length(); i++) {
char currentChar = str.charAt(i);
// ✅ 步骤1：将当前字符加入答案路径
ans.append(currentChar);
// ✅ 步骤2：从原字符串中移除该字符（构建剩余待选序列）
str.deleteCharAt(i);
// ✅ 步骤3：递归处理剩余字符
permutations(str, ans);
// ⚠️ 关键：回溯还原！必须严格逆序执行
// 步骤4：从答案中移除最后添加的字符（注意：不是 deleteCharAt(i)，而是末尾！）
ans.deleteCharAt(ans.length() - 1);
// 步骤5：将当前字符插回原位置，恢复 str 状态
str.insert(i, currentChar);
}
}
public static void main(String[] args) {
StringBuilder input = new StringBuilder("abc");
StringBuilder answer = new StringBuilder();
permutations(input, answer);
}
}输出结果：
abc acb bac bca cab cba
✅ 核心要点解析：
立即学习“Java免费学习笔记（深入）”；
- ans.append(...) 和 ans.deleteCharAt(ans.length() - 1) 构成一对原子操作：添加 → 递归 → 撤销，确保每层递归的 ans 独立且干净；
- str.deleteCharAt(i) 后，str 长度减 1，后续索引整体前移；因此回溯时必须用 str.insert(i, ch) 将字符插回原下标 i（而非 replace 或 append），否则位置错乱导致 StringIndexOutOfBoundsException；
- ❌ 原代码中 ans.deleteCharAt(i) 是典型错误：i 是原字符串的索引，而 ans 当前长度可能远大于 i，且其末尾字符位置恒为 ans.length()-1；
- ❌ newstr.replace(i, i, ...) 逻辑错误：replace(start, end, ...) 的 end 是排他性索引，replace(i,i,...) 相当于在位置 i 插入，但此时 i 已越界（因 deleteCharAt(i) 后 newstr.length() 减小）。
? 进阶建议：
- 若需收集所有排列而非仅打印，可将 System.out.println(ans) 替换为 resultList.add(ans.toString())；
- 对含重复字符的字符串（如 "aab"），可在循环内增加去重判断：if (i == 0 || str.charAt(i) != str.charAt(i-1))（需先排序）；
- 时间复杂度仍为 O(n×n!)，但 StringBuilder 显著降低常数因子，尤其对长字符串更友好。
掌握 StringBuilder 在回溯中的“修改–递归–还原”三步法，是写出高效、无 Bug 递归算法的关键能力。
