当前位置：首页 > article >正文

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

article 2024/9/18 21:35:36

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

第0004页 · 生成括号对

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

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

IO要求示例

输入描述：

一个数 n (1 <= n <= 10) 表示小括号的对数
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;
}