c++中如何求字符串的所有全排列_c++递归实现全排列算法

std::next_permutation是最简全排列实现，需先排序字符串，原地生成不重复排列；含重复字符时须排序后在循环内用used数组和相邻相等判断剪枝，传引用需手动回溯，set去重效率低且掩盖逻辑缺陷。

用 std::next_permutation 最简实现所有全排列

如果字符串字符不重复，且你只需枚举全部排列（不要求递归过程），std::next_permutation 是最稳妥、最不易出错的选择。它在 中，原地修改，时间复杂度 O(n!)，但常数极小，且自动跳过重复排列（当输入已排序时）。

注意：必须先对字符串排序，否则会漏掉部分排列；若含重复字符，它仍能去重——前提是相同字符相邻。

include 
#include 
#include 
#include 

int main() {
    std::string s = "abc";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << "\n";
    } while (std::next_permutation(s.begin(), s.end()));
}

手写递归回溯时如何避免重复排列

当字符串含重复字符（如 "aab"），直接交换+递归会产生大量重复结果。关键不是“剪枝逻辑难”，而是剪枝位置容易放错：必须在每层递归的「循环内」判断是否跳过当前字符，而不是在进入递归前检查。

• 用 std::vector used 标记位置是否被选过
• 每次循环开始前，检查 s[i] == s[i-1] && !used[i-1] —— 这表示上一个相同字符没被用，说明它属于更早分支，当前这个应跳过
• 必须先 sort(s.begin(), s.end())，否则 s[i] == s[i-1] 无法保证相邻

递归函数参数设计：传值 vs 传引用 + 回溯

传值（string cur）写起来直观，但频繁拷贝字符串开销大，尤其长度 > 10 时明显变慢；传引用（string& cur）必须手动回溯（cur.pop_back()），少一步就错。

常见错误：

• 传引用但忘记在递归调用后恢复状态（即没写 cur.pop_back()）→ 输出全是长串
• 传值却在递归内修改原串（如误用 cur += s[i] 后没返回新串）→ 逻辑断裂
• 用 substr 构造新串传入，但没控制好起始索引 → 跳过字符或越界

为什么不用 std::set 去重

有人试图把所有递归生成的排列塞进 std::set 再遍历输出，这在小数据下看似可行，但实际是陷阱：

• 时间爆炸：O(n! × log(n!))，而正确剪枝是 O(n! × n)
• 内存暴涨：全存下来可能吃光几百 MB，尤其 n=12 时已有 4.79e8 种排列（无重复时）
• 掩盖逻辑缺陷：不去重≠不会写错，反而让 bug 更隐蔽

真正难的不是“怎么列出来”，而是“怎么确保每个排列只生成一次”。递归中靠排序+相邻判断剪枝，比事后去重靠谱得多。