std::next_permutation 是最直接的方式，只要数组元素可比较（如 int、char 或自定义类型重载了 operator<）。
用 std::next_permutation 是最直接的方式
只要数组元素可比较（比如 int、char、自定义类型重载了 ），<code>std::next_permutation 就能原地生成字典序下一个排列，且时间复杂度稳定在 O(1) 均摊。它要求输入初始为升序（或至少是非降序），否则会漏掉前面的排列。
常见错误是传入未排序的数组后直接调用，结果只输出部分排列甚至一次都不进循环。正确做法是先调用 std::sort。
- 必须包含头文件：
#include <algorithm></algorithm> - 输入容器需支持随机访问迭代器（
std::vector、原生数组都行） - 函数返回
bool：成功生成下一个排列返回true，已是最后一个排列则返回false - 原地修改，不分配新内存，空间效率高
std::vector<int> arr = {1, 2, 3};
std::sort(arr.begin(), arr.end());
do {
for (int x : arr) std::cout << x << ' ';
std::cout << '\n';
} while (std::next_permutation(arr.begin(), arr.end()));
处理含重复元素的数组要先去重逻辑？不，用 std::next_permutation 本身就能去重
很多人误以为含重复元素就得手动跳过，其实 std::next_permutation 生成的是「字典序唯一排列」——它内部按严格小于比较，天然跳过重复序列。前提是你的元素类型比较行为一致，比如 std::vector<int></int> 没问题，但若用自定义结构体，必须确保 operator 正确反映“值相等即不可区分”。
反例：如果写了一个按 id 排序但忽略 name 的 operator，而两个对象 id 相同 name 不同，<code>next_permutation 可能生成逻辑上重复的排列（因为比较认为它们“相等”）。
立即学习“C++免费学习笔记（深入）”；
- 重复元素无需预处理，也不用
std::unique - 保证
operator 是全序且与“值相等”语义一致 - 若需保留原始顺序再生成所有不重复排列（如输入是 {2,2,1}），仍需先
sort，否则起始点不是字典序最小，会漏解
手写递归回溯适合理解原理，但要注意交换和恢复的时机
当需要控制中间状态（比如剪枝、记录路径深度、绑定索引位置）时，手写回溯更灵活。核心是：每轮固定一个位置，枚举该位置所有可能的未使用元素，递归填下一个位置，返回前必须撤销交换（backtrack）。
容易踩的坑是忘记恢复数组状态，导致后续分支看到脏数据；或者在循环内重复使用同一元素（没用 visited 标记或没做 swap 隔离）。
- 推荐用索引
pos表示当前要填的位置，范围是[0, n) - 对每个
i从pos到末尾，swap(arr[pos], arr[i])后递归，返回后再swap回来 - 若元素有重复且不想生成重复排列，可在循环内加判断：
if (i > pos && arr[i] == arr[i-1]) continue（前提是已排序） - 避免 vector 的 push/pop，改用索引传递更轻量
性能和边界要注意：原生数组传参别退化成指针
用原生数组（如 int arr[4]）调用 next_permutation 时，务必传迭代器范围，别传指针加长度——next_permutation(arr, arr + 4) 正确，next_permutation(arr, 4) 编译不过。C++ 没有内置接受指针+长度的重载。
另外，全排列数量是 n!，n ≥ 12 就超 4.7 亿，实际运行中很容易卡住或爆内存（尤其递归栈）。没有剪枝需求时，优先用 next_permutation 迭代式；真要 n ≥ 10，得确认业务是否真的需要全部结果，还是只需计数、找第 k 个、或带约束条件。
最后提醒：std::next_permutation 修改的是元素值顺序，不改变元素本身（比如 string 或自定义对象的成员），所以深拷贝成本高的场景，考虑只排列索引（vector<size_t></size_t>），再用它间接访问原数据。
