自己动手实现排列与组合
较难5自己动手实现排列与组合：用递归轻松搞定
在日常生活中，我们经常会遇到“排列”和“组合”的问题。比如：老师要从5个同学中选3个去参加比赛，有多少种选法？这就是组合（顺序不重要）。如果还要给这3个同学排一个出场顺序（谁先谁后），那就是排列（顺序重要）。很多编程语言都有现成的函数（比如C++的next_permutation）来生成排列组合，但如果你想真正理解它们是怎么一步步“变”出来的，最好的方法就是自己动手写一个递归版本。
下面，我们就用递归（函数调用自己）的方法，分别实现全排列和组合。递归的特点像“套娃”——一层层往里钻，到底后再一层层返回，每一步都清清楚楚。我们还会用到“回溯”的思想：先尝试一种选择，做完后恢复现场，再尝试另一种选择。就像你玩走迷宫，走到死路就退回到上一个岔路口，换一条路继续走。
一、全排列：给一堆元素排顺序
假设你有三个同学：小A、小B、小C，想让他们拍照站成一排，有多少种站法？答案是3! = 6种。用递归实现的思路是：先固定第一个位置，然后让剩下的人排剩下的位置，如此重复。
递归思路：固定一个，处理剩下的
我们把数组分成两部分：左边是“已经固定好的前缀”，右边是“还没处理的剩余元素”。每次从右边挑一个放到前缀末尾，然后递归处理剩下的。等递归返回后，一定要把刚才交换的两个元素换回来，这就是回溯。
举个例子，对于数组 {1, 2, 3}：
- 先固定第一个位置：可以选1、2或3。
- 如果选1，剩下的就是{2,3}，继续递归。
- 固定第二个位置：可以选2或3。
- 如果选2，剩下的{3}放在第三位，得到排列 [1,2,3]。
- 如果选3，得到 [1,3,2]。
- 固定第二个位置：可以选2或3。
- 如果选2，剩下{1,3}，递归得到 [2,1,3] 和 [2,3,1]。
- 如果选3，剩下{1,2}，递归得到 [3,1,2] 和 [3,2,1]。
- 如果选1，剩下的就是{2,3}，继续递归。
代码实现（带详细注释）
#include <iostream>
#include <vector>
using namespace std;
// 递归生成所有排列
// arr: 待排列的数组，start: 当前要固定的位置（从0开始）
void permute(vector<int>& arr, int start) {
// 如果已经固定到最后一个元素，说明一轮排列完成，输出
if (start == arr.size()) {
for (int x : arr) cout << x << " ";
cout << endl;
return;
}
// 从 start 开始，依次把每个元素放到当前位置
for (int i = start; i < arr.size(); i++) {
swap(arr[start], arr[i]); // 把第i个元素换到当前固定位置
permute(arr, start + 1); // 递归固定下一个位置
swap(arr[start], arr[i]); // 还原（回溯），保证数组恢复原样
}
}
int main() {
vector<int> arr = {1, 2, 3}; // 待排列的数组
permute(arr, 0); // 从第0个位置开始固定
return 0;
}
运行结果：
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
你可能会问：为什么每次递归完要交换回来？因为如果不还原，数组的顺序就会被打乱，下一次循环选的元素就不对了。比如第一次循环选了arr[0]和arr[0]交换（不动），递归完成后数组是[1,2,3]。第二次循环选arr[0]和arr[1]交换，变成[2,1,3]，递归完成后如果不换回来，数组就是[2,1,3]，那第三次循环arr[0]和arr[2]交换就变成了[3,1,2]，而不是正确的[3,2,1]。所以必须还原。
二、组合：从一堆元素中选几个
组合和排列不同，组合不关心顺序。比如从1~5这5个数中选3个，{1,2,3}和{3,2,1}是同一种组合。用递归实现组合的经典方法是：对每个元素，决定“选”还是“不选”，直到选够了m个或者所有元素都考虑完了。
递归思路：选或不选
想象你面前有一排零食：薯片、巧克力、糖果、饼干、果冻。你想选3样当零食吃。你可以从第一个开始：拿起薯片（选），然后考虑下一个；或者跳过薯片（不选），直接看下一个。继续这个过程，直到你手里有3样零食，或者看完了所有零食。
这种“选或不选”的决策树就是组合递归的骨架。我们用 index 表示当前考虑第几个元素，用 cur 表示当前已经选中的元素列表。
代码实现（带详细注释）
#include <iostream>
#include <vector>
using namespace std;
// 从 items 中选 m 个，递归生成所有组合
// items: 总元素列表，m: 要选几个，index: 当前考虑的元素下标，cur: 当前已选中的元素
void combine(const vector<int>& items, int m, int index, vector<int>& cur) {
// 如果已经选了 m 个，输出当前组合
if (cur.size() == m) {
for (int x : cur) cout << x << " ";
cout << endl;
return;
}
// 如果已经越界（没有更多元素了），返回
if (index >= items.size()) return;
// 情况1：选当前元素 items[index]
cur.push_back(items[index]); // 把它加入已选列表
combine(items, m, index + 1, cur); // 递归处理下一个元素
cur.pop_back(); // 回溯：移除刚才选的元素
// 情况2：不选当前元素
combine(items, m, index + 1, cur); // 直接跳过，考虑下一个
}
int main() {
vector<int> items = {1, 2, 3, 4, 5}; // 总共有5个数
int m = 3; // 每次选3个
vector<int> temp; // 临时存放已选的数
combine(items, m, 0, temp);
return 0;
}
运行结果（部分）：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
注意：组合不考虑顺序，所以输出里只有从小到大排列的序列。这是因为我们总是按索引递增的顺序去“选或不选”，不会出现先选后面的再选前面的情况，自然避免了重复。
三、新手常见错误
1. 忘记回溯（还原）
在排列中，忘了在递归后面加 swap(arr[start], arr[i])，会导致数组被破坏，输出重复或错误的排列。在组合中，忘了 cur.pop_back()，会导致 cur 越加越多，永远选不够m个（或者选到后面全乱套）。
解决方法：每次递归调用后，立即还原现场，养成习惯。
2. 索引越界
组合代码中，如果不检查 index >= items.size()，递归会无限调用下去直到栈溢出。排列中，如果 start 传入超过 arr.size() 的值，也会出错。务必加上递归终止条件。
3. 引用传递导致修改原数组
在排列函数中，参数 arr 是引用（vector<int>&），所以递归中交换会影响原数组。这是有意设计的，因为我们需要在同一个数组上操作。但如果你不小心在递归中修改了数组而没有还原，后果就是排列不全。注意引用传递的副作用。
4. 组合结果顺序不对
如果你希望组合结果按照某种顺序（比如字典序）输出，可以预先对 items 排序。上述代码中 items 已经有序，所以输出也是字典序。
四、完整可运行示例
下面我们把排列和组合两个程序整合到一起，方便你复制运行。
#include <iostream>
#include <vector>
using namespace std;
// ============ 全排列 ============
// arr: 数组（引用），start: 当前固定位置
void permute(vector<int>& arr, int start) {
if (start == arr.size()) {
for (int x : arr) cout << x << " ";
cout << endl;
return;
}
for (int i = start; i < arr.size(); i++) {
swap(arr[start], arr[i]); // 交换
permute(arr, start + 1); // 递归
swap(arr[start], arr[i]); // 回溯
}
}
// ============ 组合 ============
// items: 总元素列表，m: 要选几个，index: 当前下标，cur: 已选列表
void combine(const vector<int>& items, int m, int index, vector<int>& cur) {
if (cur.size() == m) {
for (int x : cur) cout << x << " ";
cout << endl;
return;
}
if (index >= items.size()) return;
// 选当前元素
cur.push_back(items[index]);
combine(items, m, index + 1, cur);
cur.pop_back();
// 不选当前元素
combine(items, m, index + 1, cur);
}
int main() {
cout << "===== 全排列测试 =====" << endl;
vector<int> arr = {1, 2, 3}; // 待排列的数组
cout << "数组 [1,2,3] 的所有排列：" << endl;
permute(arr, 0);
cout << "\n===== 组合测试 =====" << endl;
vector<int> items = {1, 2, 3, 4, 5}; // 总共有5个数
int m = 3; // 选3个
vector<int> temp; // 临时存放
cout << "从[1,2,3,4,5]中选3个的所有组合：" << endl;
combine(items, m, 0, temp);
return 0;
}
运行这个程序，你会看到清晰的输出，对照着代码理解每一步。
五、相关知识点指引
next_permutation：C++标准库提供的全排列函数，按字典序递增生成下一个排列。如果你不想自己写递归，可以直接用这个函数。但理解递归实现能帮你更清楚它内部干了什么。- 二进制枚举：对于组合，还有一种用二进制位表示选或不选的方法，适合元素个数较少的情况（比如不超过32个）。它利用整数的二进制位，0表示不选，1表示选。
- 回溯算法：排列和组合是回溯算法的经典应用。回溯的核心是“尝试-递归-还原”，常用于解决“所有可能解”的问题，比如八皇后、数独、迷宫寻路等。
- 剪枝优化：在组合递归中，如果当前已选数量加上剩余数量仍然不够m，可以提前终止（即“剪枝”），提升效率。你可以试着在
combine函数里加上这个判断：if (cur.size() + items.size() - index < m) return;。
希望这篇文章能帮你彻底搞懂排列和组合的递归实现。自己动手写一遍，加上 cout 打印每次递归的状态，会更有感觉哦！
例题精讲
在实现一个递归函数来生成数组所有排列时，通常采用“交换-递归-回溯”的模式。请问在递归函数中，当处理到第index个位置时，应该将index与哪些元素交换？
使用C++标准库函数std::next_permutation生成所有排列时，必须先将序列按升序排序，否则无法生成全部排列。
以下代码实现从1到n中选取k个数的所有组合（回溯法）。请填写缺失的部分。
void combine(vector<vector<int>>& res, vector<int>& cur, int n, int k, int start) {
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = start; i <= n; ++i) {
cur.push_back(i);
combine(res, cur, n, k, ___);
cur.pop_back();
}
}在实现计算组合数C(n,k)时，直接计算阶乘容易导致整数溢出。以下哪种方法在不使用大数库的情况下更安全且高效？
以下函数使用std::next_permutation生成数组nums的所有排列。请填写循环条件。
vector<vector<int>> permute(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
do {
res.push_back(nums);
} while (___);
return res;
}