Module: 递归枚举


Problem

1 /4


所有PSP

Theory Click to read/hide

在大多数情况下,枚举问题都是通过递归枚举来解决的。不幸的是,没有通用的方法,因为通常,迭代方法高度依赖于任务本身。
但是,可以注意到各种组合对象的枚举方法之间存在一些相似之处。因此,作为一个说明性示例,请考虑生成从 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; }  
在递归迭代中,应始终特别注意递归切割。实际上,它们可以大大加快程序的速度。

Problem

给定编号 n。您需要生成包含 n 对括号的所有有效括号序列。

输入:
第一行包含一个自然数 n (1 <= n <= 8)。

输出:
按字典顺序升序打印所有正确的括号序列。每个单独一行。

示例:
  <正文>
输入 输出
3 ((()))
(()())
(())()
()(())
()()()