如何用C语言实现包含全排列和递归与STL方法的组合长尾词？

本文共计911个文字，预计阅读时间需要4分钟。

该代码段使用 `std::next_permutation` 函数来找到当前序列的下一个排列。如果已经到达序列的最后一个排列，则该函数返回 `false`，表示已无更多排列。以下是代码的简单解释：

• 错误写法：vector<int> v = {3, 1, 2}; do { ... } while (next_permutation(v.begin(), v.end()));</int> —— 会直接从 {3,1,2} 的下一个（即 {3,2,1}）开始，漏掉 {1,2,3} 到 {3,1,2} 之间的全部
• 正确做法：先 sort(v.begin(), v.end())，再用 do { ... } while (next_permutation(v.begin(), v.end()));
• 注意：next_permutation 修改原容器，若需保留原始顺序，得先拷贝

递归实现全排列时重复元素怎么去重

原始递归模板对含重复元素的数组会输出大量重复排列，关键不是“跳过相同值”，而是“跳过同一层已选过的相同值”。

• 必须在每层递归中维护一个局部 set 或布尔数组，记录该位置已尝试过哪些值
• 不能只写 if (i > 0 && nums[i] == nums[i-1]) continue; —— 这只在数组有序且未标记使用状态时部分有效，但极易漏判
• 推荐做法：排序后 + used 数组 + 每层用 unordered_set<int></int> 记录本层已选数值
• 示例片段：if (used[i] || seen.count(nums[i])) continue;，循环内更新 seen.insert(nums[i]);

vector 和 string 做全排列性能差在哪

本质是拷贝开销。每次递归传 vector 值参或拼接 string 都触发深拷贝，n 层递归可能产生 O(n·n!) 级别内存操作。

• 优化方向：统一用索引操作 + 引用传参，全程只操作原始容器
• string 比 vector<char></char> 更易误写成值传递；vector<int></int> 在交换元素时比 int[] 多一次边界检查（Release 模式下可忽略）
• 实测：对长度为 10 的数组，引用+回溯比值传递快 3–5 倍（Clang 16 -O2）
• STL 方法中 next_permutation 是就地修改，无额外分配，是大规模枚举的首选

LeetCode 46/47 题用 STL 过不了？检查这几个点

不是 next_permutation 不行，而是输入预处理和结果收集逻辑常出错。

立即学习“C++免费学习笔记（深入）”；

• LeetCode 47（含重复）必须先 sort 输入，否则 next_permutation 无法保证覆盖全部唯一排列
• 结果容器如果用 set<vector>></vector> 去重，时间爆炸——应靠排序+跳过连续重复来避免生成重复，而非事后过滤
• 常见错误：在 do-while 循环外提前 push_back 一次，导致首排列被加两次
• 边界 case：nums = {} 或 {1}，next_permutation 对单元素返回 false，需单独处理空输入

递归路径管理和 STL 迭代器状态是两套完全不同的控制流，混用容易错乱；尤其在需要中途剪枝或自定义顺序时，手写递归反而更可控。