如何修改递归函数实现仅打印字符串的无重复唯一全排列

原函数未处理输入字符串含重复字符的场景，当剩余待选字符（rest）中存在多个相同字符时，选择不同位置的相同字符会生成完全一致的排列路径，最终导致重复输出相同结果。修改核心逻辑为同一递归层级内每个不同字符仅选择一次，避免生成重复分支，以下是两种实现方案：

方案1：哈希集合去重（无需预排序，通用性强） #

通过额外的哈希集合记录当前递归层已经使用过的字符，遇到重复字符直接跳过即可：

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

void RecPermute(string soFar, string rest) {
  if (rest == "")           // 无剩余字符，输出唯一排列
    cout << soFar << endl;
  else {
    unordered_set<char> used; // 记录当前层已使用的字符
    for (int i = 0; i < rest.length(); i++) {
      // 跳过当前层已选过的重复字符
      if (used.count(rest[i]))
        continue;
      used.insert(rest[i]);
      string next = soFar + rest[i];
      string remaining = rest.substr(0, i) + rest.substr(i + 1);
      RecPermute(next, remaining);
    }
  }
}
// 包装调用函数
void ListPermutations(string s) {
  RecPermute("", s);
}

方案2：排序后相邻去重（空间开销更低） #

如果希望节省哈希集合的额外空间，可以先对输入字符串排序让相同字符相邻，之后循环时直接跳过和前一位相同的字符即可：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void RecPermute(string soFar, string rest) {
  if (rest == "")
    cout << soFar << endl;
  else {
    for (int i = 0; i < rest.length(); i++) {
      // 排序后相同字符相邻，跳过重复字符
      if (i > 0 && rest[i] == rest[i-1])
        continue;
      string next = soFar + rest[i];
      string remaining = rest.substr(0, i) + rest.substr(i + 1);
      RecPermute(next, remaining);
    }
  }
}

void ListPermutations(string s) {
  sort(s.begin(), s.end()); // 先排序让相同字符相邻
  RecPermute("", s);
}

内容的提问来源于stack exchange，提问作者Doha Hanafy