回溯法生成全排列的核心逻辑是「交换 + 递归 + 恢复」：固定位置、循环尝试未用元素、递归处理后续、返回前恢复状态；需引用传递vector、设终止条件path.size()==nums.size()、排序+!used[i-1]去重；next_permutation仅适用于可排序且无需剪枝的场景。
回溯法生成全排列的核心逻辑是什么
关键在于「交换 + 递归 + 恢复」：每次固定一个位置，用循环尝试所有未使用过的元素填入该位置，递归处理后续位置，返回前把交换操作撤销（即回溯）。不恢复会导致后续分支看到错误状态，结果重复或遗漏。
常见错误现象：std::vector 传参没用引用导致拷贝开销大、递归没写终止条件、忘记在递归调用后 swap 回原值。
- 必须用引用传递
std::vector<int>& path</int>和std::vector<bool>& used</bool>，否则每层递归都复制整个路径和标记数组 - 终止条件是
path.size() == nums.size()，此时保存一份path的拷贝到结果中 - 每轮
for循环里，先used[i] = true，再push_back，递归，再pop_back和used[i] = false
如何避免重复元素导致的重复排列
当输入含重复数字（如 [1,1,2]），直接按基础回溯会输出重复排列。根本原因是：相同数字在不同索引位置被当作不同元素参与了交换。
解决方法是在循环内跳过「已用过」或「与前一个相同且前一个未被使用」的元素——后者是关键判断点，它确保相同数字只由「第一个未被使用的」来主导本轮选择。
立即学习“C++免费学习笔记（深入）”；
- 先对
nums排序：std::sort(nums.begin(), nums.end()) - 循环中加判断：
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; - 注意不是
used[i-1]而是!used[i-1]：只有前一个相同数还没被选时，当前这个才跳过；如果前一个已被选，说明它是本层递归中「第一个出现的相同数」，应当允许
std::next_permutation 能否替代手写回溯
可以，但适用场景不同。std::next_permutation 要求输入已排序，且只能按字典序生成下一个排列，不能中途剪枝、不能自定义约束（比如只保留偶数开头的排列）。
性能上，std::next_permutation 是单次 O(n) 的迭代实现，整体 O(n! × n)，而手写回溯在剪枝后可能显著减少实际递归层数。
- 若只需枚举全部排列且输入可排序，用
do { ... } while (std::next_permutation(nums.begin(), nums.end()));更简洁 - 若需在生成过程中加入条件判断（如跳过某类中间状态）、或输入不可修改（只读
const std::vector<int>&</int>），必须手写回溯 - 注意
std::next_permutation修改原容器顺序，如需保持原始顺序，得先拷贝一份
为什么用 std::vector<bool></bool> 标记已使用元素比用 std::set 更合适
因为索引访问是 O(1)，而 std::set 查找是 O(log n)。全排列总节点数是 O(n!)，每层都要检查是否已用，累计开销差异明显。
更隐蔽的问题是：用 std::set 存值（而非索引）无法区分重复元素的不同位置，导致逻辑混乱；而 used[i] 明确对应第 i 个位置的元素是否被选，天然支持去重逻辑中的 i-1 判断。
-
std::vector<bool> used(nums.size(), false)</bool>初始化即可，空间 O(n) - 不要用
std::find(used.begin(), used.end(), nums[i]) != used.end()这类写法——这是查值，不是查索引，完全错误 -
std::vector<bool></bool>是特化类型，某些老编译器可能有代理对象陷阱，但用于标记访问完全安全
真正容易被忽略的是：回溯函数内部的变量作用域边界。比如在 for 循环外声明 int i，然后在循环里用 used[i]，一旦递归嵌套，外层 i 可能被内层修改覆盖。务必让所有循环变量是 for (int i = 0; ...) 这种局部作用域。
