一、排列基础概念
排列定义：从n个元素中取出所有元素按顺序排布，所有不同的有序组合即为全排列，顺序不同视为不同结果。
排列数公式：n个元素的全排列总数为 n! = n × (n-1) × ... × 1，例如3个元素的全排列共6种。
字典序规则：排列之间按从左到右逐位比较大小，是C++排列生成的默认排序规则。
二、方法1：STL库next_permutation快速实现
这是最简便的工业级写法，无需手动实现复杂逻辑。
核心依赖：需要引入头文件 <algorithm>。
关键注意点：必须先对数组执行sort排序，否则会跳过字典序小于初始序列的排列。
基础代码示例：
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int num[] = {1, 2, 3};
// 先排序保证从最小字典序开始生成
sort(num, num + 3);
do {
cout << num << " " << num << " " << num << endl;
} while (next_permutation(num, num + 3));
return 0;
}
扩展用法：支持字符串、自定义类型，自定义类型需重载<运算符或传入自定义比较函数。
性能优势：迭代实现无递归栈开销，比手写递归快2~3倍，适合常规遍历场景。
三、方法2：DFS回溯法实现全排列
这是经典的回溯算法教学实现，便于自定义剪枝逻辑。
核心思路：逐个填充排列的每一个空位，用标记数组记录已使用的元素，填充完所有位置后输出结果，再回溯撤销选择尝试其他分支。
完整代码示例：
#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<int>& state, const vector<int>& choices,
vector<bool>& selected, vector<vector<int>>& res) {
// 排列长度等于元素总数，记录结果
if (state.size() == choices.size()) {
res.push_back(state);
return;
}
for (int i = 0; i < choices.size(); i++) {
if (!selected[i]) {
// 做出选择
selected[i] = true;
state.push_back(choices[i]);
// 递归进入下一层选择
backtrack(state, choices, selected, res);
// 回溯撤销选择
selected[i] = false;
state.pop_back();
}
}
}
int main() {
vector<int> nums = {1, 2, 3};
vector<int> state;
vector<bool> selected(nums.size(), false);
vector<vector<int>> res;
backtrack(state, nums, selected, res);
// 输出所有排列
for (auto& arr : res) {
for (int x : arr) cout << x << " ";
cout << endl;
}
return 0;
}
四、方法3：交换法实现全排列
无需额外标记数组，通过交换元素原位生成排列，空间复杂度更低。
核心思路：把数组分为已固定前缀和待排列后缀，每次将后缀中的一个元素交换到当前固定位置，递归处理后续位置，递归结束后交换回原位回溯。
完整代码示例：
#include <iostream>
#include <vector>
using namespace std;
void permute(vector<int>& nums, int l, int r) {
if (l == r) {
for (int x : nums) cout << x << " ";
cout << endl;
return;
}
for (int i = l; i <= r; i++) {
swap(nums[l], nums[i]);
permute(nums, l + 1, r);
swap(nums[l], nums[i]); // 回溯恢复原数组
}
}
int main() {
vector<int> nums = {1, 2, 3};
permute(nums, 0, 2);
return 0;
}
五、含重复元素的全排列处理
当输入存在重复元素时，朴素实现会生成大量重复排列，需要通过剪枝去重。
核心剪枝规则：先排序让相同元素相邻，递归时判断如果当前元素和前一个元素相等且前一个元素未被使用，就跳过当前分支。
关键代码片段：
// 排序使相同元素相邻
sort(nums.begin(), nums.end());
// 循环内剪枝判断
if (i > 0 && nums[i] == nums[i-1] && !selected[i-1]) continue;
