【第0004页 · 递归】生成括号对

本文主要是介绍【第0004页 · 递归】生成括号对，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【前言】本文以及之后的一些题解都会陆续整理到目录中，若想了解全部题解整理，请看这里：

第0004页 · 生成括号对

        今天这题有点难绷，从某种程度上来说应该是第二次写这个问题了，但还是卡住了，现在我们来看一下这个问题。

 【生成括号对】 给定正整数 n，生成 n 对小括号，输出所有可能的解决方案。（注：合法方案要求满足：1、共有 n 个左小括号和 n 个右小括号；2、每对小括号都可以匹配）例如："()()" 和 "(())" 是合法方案，但是 "(()" 不是合法方案。

IO要求	示例
输入描述： 一个数 n (1 <= n <= 10) 表示小括号的对数	2
输出描述： 每行一个合法小括号对。结果按字典序升序输出。	(()) ()()

 【解题分析】这道题我们考虑使用递归的想法来解决。在 C++ 中有一种标准容器叫做 set 集合，利用这种容器的唯一性和自动升序排列性，我们直接就可以构建一个全局的 set 容器，将所有可能的情况都存入这个容器中，让它自动排序，最后统一输出。接下来，我们来思考对于 n 对小括号的情况，我们应该怎么考虑这个问题。

        首先，我们为了减少一些重复构建容器的过程，我们可以创建一个标记性数组，这个数组中每个元素都是一个 set 容器，第 i 个元素用来存储含有 i 对小括号的合法方案的 set 集合。

        接着，我们思考合法方案有两种可能：1、整个字符串可以拆分为多个 ()()...，例如："(())()" 就可以拆分为 "(())" 和 "()"。2、整个字符串不能被拆分，只能看作 "( substr )"，例如："(()())" 中 只能将其看成上面的形式，其中 substr = "()()"。

        综合以上分析，我们就可以完成整个程序的编写了。

【源码展示】

#include <cstdio>
#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;const int MAXN = 10 + 1;
set<string> hashedResults[MAXN];set<string> DFS(int n) {if (hashedResults[n].size() > 0) {return hashedResults[n];}set<string> results;for (int i = 1; i < n; i++) {set<string> leftResults = DFS(i);set<string> rightResults = DFS(n - i);for (auto leftResult: leftResults) {for (auto rightResult: rightResults) {results.insert(leftResult + rightResult);}}}set<string> subResults = DFS(n - 1);for (auto subResult: subResults) {results.insert("(" + subResult + ")");}hashedResults[n] = results;return results;
}int main() {int n;scanf("%d", &n);hashedResults[0].insert("");set<string> results = DFS(n);for (auto result: results) {cout << result << endl;}return 0;
}

这篇关于【第0004页 · 递归】生成括号对的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---