在大多数情况下，枚举问题都是通过递归枚举来解决的。不幸的是，没有通用的方法，因为通常，迭代方法高度依赖于任务本身。
但是，可以注意到各种组合对象的枚举方法之间存在一些相似之处。因此，作为一个说明性示例，请考虑生成从 n 到 k 的所有组合的代码。
诠释 n, k;
// 支持组合前缀的数组。
//
// 本例中的前缀表示我们选择了组合中的一些对象。
//
// 随后，它们将以正确的组合完成，
// 否则递归会在意识到无法正确完成这样的前缀时切断分支
向量 arr;
// 递归迭代函数本身
//
// pos - 组合对象的编号，我们将在当前时刻确定（从 0 到 k - 1）
//
// prev - 上一步取的对象的值
//
// 在组合中，对象的顺序并不重要（[1, 2] 和 [2, 1] 被认为是相同和相似的），
// 所以我们只想生成对象值升序排列的集合。
//
// 这是必要的，这样 [1, 2] 和 [2, 1] 等相同的选项只会迭代一次
//（在我们的例子中，我们只考虑 [1, 2]，而不考虑 [2, 1]，因为它不是有序集）。
//
// 这就是为什么我们保留 prev 变量以减少迭代次数
void rec(int pos, int prev) {
// 如果选中的元素个数等于k，那么我们已经选中了所有元素
// 因为他们的编号是从 0 到 k - 1
如果（pos == k）{
// 如果满足条件，则正确的组合现在在 arr 数组中
// 我们可以以某种方式处理它（在这种情况下，只需将它打印到控制台）
for (int i = 0; i < k; i++)
输出 << arr[i] + 1 <<; ' ';
输出 << '\n'
返回; // 切断递归分支，因为已经得到组合，无需继续
}
// 在这里我们检查我们是否可以从剩余的元素中得到正确的组合
// 如果没有足够的剩余元素，那么我们切断这个递归分支
if (k - pos > n - prev - 1)
返回;
// 迭代我们放置在索引为 pos 的位置上的对象
// 但是因为我们想要一个有序集合，那么最小可能值为 prev + 1
for (int i = prev + 1; i < n; i++) {
arr.push_back(i); // 向全局数组添加一个元素。现在我们似乎选择了他
rec(pos + 1, i); //递归运行以设置以下项目
arr.pop_back(); // 从递归返回后，我们当前选择的元素不再相关，
// 因为在递归中，我们遍历了所有带有这样一个前缀的选项，
// 所以这个元素需要被移除
}
}
主函数()
{
辛＞＞ n>> k;
// 最初我们将元素设置在第 0 个位置
// 我们假设之前选择了元素 -1，因此迭代最初是从一个空对象开始的
记录（0，-1）；
返回 0；
}
相同的代码，但没有注释：
诠释 n, k;
向量 arr;
void rec(int pos, int prev) {
如果（pos == k）{
for (int i = 0; i < k; i++)
输出 << arr[i] + 1 <<; ' ';
输出 << '\n'
返回;
}
if (k - pos > n - prev - 1)
返回;
for (int i = prev + 1; i < n; i++) {
arr.push_back(i);
rec(pos + 1, i);
arr.pop_back();
}
}
诠释主要（）{
辛＞＞ n>> k;
记录（0，-1）；
返回 0；
}
在递归迭代中，应始终特别注意递归切割。实际上，它们可以大大加快程序的速度。
|