括号生成

数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

  • 示例 1：

    输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

  • 示例 2：

    输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> results;
        if (n == 0) {
            results.emplace_back("");
            return results;
        }
        for (int i = 0; i < n; ++i) {
            vector<string> lefts = generateParenthesis(i);
            vector<string> rights = generateParenthesis(n - i - 1);
            for (string left: lefts) {
                for (string right: rights) {
                    string result = "(" + left + ")" + right;
                    results.emplace_back(result);
                }
            } 
        }
        return results;
    }
};

int main() {
    vector<string>  results;
    results = Solution().generateParenthesis(3); // ["((()))","(()())","(())()","()(())","()()()"]
    for (int i = 0; i < results.size(); ++i) {
        std::cout << results.at(i) << " ";
    }
}