跳转到主内容
极星编程网：以代码为星，赴技术山海！
📁 网站地图

C++怎么实现字符串全排列_C++递归回溯算法示例【实战】

苏承栈
苏承栈
• 👁 0人浏览过
用std::next_permutation不漏解需先排序再do-while循环；它自动去重且性能优于手写回溯；string上swap失效多因传值或const引用。 std::next_permutation 怎么用才不漏解 直接用
std::next_permutation
是最稳妥的全排列实现方式，前提是输入序列初始为升序（或严格弱序）。它只生成字典序下一个排列，如果起始不是最小序，会跳过前面所有排列。 必须先对字符串排序：
std::sort(s.begin(), s.end())
，否则第一次调用就可能返回
false
循环条件写成
do { ... } while (std::next_permutation(s.begin(), s.end()))
，不能用
while
前置判断，否则会丢掉原始排列 重复字符也能正确去重——只要容器元素支持
比较，next_permutation
内部自动跳过等价排列 手写递归回溯时 vector & res 传参为什么总为空 常见错误是把结果容器按值传递（
vector res
），每次递归都拷贝一份，修改的只是副本，上层看不到新增排列。 必须传引用：
void dfs(string& s, int i, vector& res)
递归终止条件别写成
i == s.length() - 1
，应该是
i == s.length()
，否则最后一个字符没参与交换，少一层分支 交换后记得回溯还原：
swap(s[i], s[j]);
后必须再 swap 一次，否则后续分支基于脏状态运行 去重逻辑不能只靠
if (j > i && s[j] == s[j-1]) continue;
——这只有在已排序前提下才有效；若未排序，得用
set
记录本轮用过的首字符 有重复字符时 std::next_permutation 和手动回溯性能差多少 两者时间复杂度都是 O(n! × n)，但常数差异明显：
next_permutation
是高度优化的底层实现，单次调用平均 O(1)；而手写回溯每层都要遍历、判重、swap，实际慢 2–3 倍。 重复字符越多，手动回溯的剪枝收益越小——因为
next_permutation
本身已内置等价跳过逻辑 若只需计数不需要存结果，用
std::next_permutation
配合计数器比构造所有字符串快一个数量级 注意：
next_permutation
要求随机访问迭代器，
std::list
不支持，必须用
std::string
或
std::vector
为什么 swap(s[i], s[j]) 在 string 上有时不生效
std::string
的
operator[]
返回的是
char&
，swap 本身没问题。问题多出在：传入的是
string
值参，或用了
const string&
，或误用
s.at(i)
（抛异常不改内容）。 立即学习 “ C++免费学习笔记（深入） ”； 确保参数是
string& s
，不是
const string&
或
string
避免用
s.c_str()[i]
—— 返回 const char*，无法赋值 调试时打印
s.data()
地址，确认每次递归操作的是同一块内存，而不是意外拷贝 实际写的时候，重复字符处理和引用传递这两个点，最容易在深夜调试时反复卡住。

相关文章