Java实现字符串全排列find_permutation方法输出异常求助

输出重复原字符串的核心原因是Java的String是不可变类型：实现的swap方法不会修改传入的原字符串，只会生成并返回交换字符后的新字符串，但permute方法中调用swap时没有接收这个返回值，导致递归全程操作的始终是最开始传入的原始字符串"ABC"，最终递归到边界时添加到结果集的自然全是重复的原字符串。

• Java中String类是不可变对象，所有对String的修改操作都会生成新的对象，不会改动原对象本身
• 现有swap方法的交换逻辑本身没有问题，确实返回了交换i、j位置后的新字符串，但在permute的循环中两次调用swap时，都没有接收返回的新字符串，局部变量S从头到尾没有发生变化，回溯逻辑也完全没有生效：

  swap(S, l, i); // 未接收返回值，S保持原值
  permute(S, l + 1, r, ans);
  swap(S, l, i); // 未接收返回值，回溯操作无效
  

• 由于上述问题，每次递归到l==r的终止条件时，S都是初始传入的"ABC"，因此结果集全是重复值。

最小改动方式是在调用swap时，将返回的新字符串重新赋值给局部变量S即可，修复后完整代码如下：

import java.util.*;
class Solution {

  public List<String> find_permutation(String S) {
    List<String> ans = new ArrayList<>();
    int l = 0, r = S.length() - 1;
    permute(S, l, r, ans);
    // 若题目要求按字典序返回结果，可放开下面这行排序代码
    // Collections.sort(ans);
    return ans;
  }

  public static void permute(String S, int l, int r, List<String> ans) {
    if (l == r) {
      ans.add(S);
      return;
    }

    for (int i = l; i <= r; i++) {
      S = swap(S, l, i); // 接收交换后的新字符串
      permute(S, l + 1, r, ans);
      S = swap(S, l, i); // 回溯时接收换回的字符串
    }
  }

  public static String swap(String S, int i, int j) {
    char[] c = S.toCharArray();
    char temp = c[i];
    c[i] = c[j];
    c[j] = temp;
    return String.valueOf(c);
  }
}

输入"ABC"测试时，修复后代码可正确输出ABC、ACB、BAC、BCA、CAB、CBA共6组全排列结果。

补充：如果输入字符串包含重复字符，上述代码会生成重复排列，可通过Set存储结果去重，或在循环交换时跳过相同字符的交换逻辑来优化。

内容的提问来源于stack exchange，提问作者Shashank Parihar