22. 括号生成

22. 括号生成 #

链接 #

题目 #

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

解答 #

class Solution {
 public:
  vector<string> generateParenthesis(int n) {
    if (n == 0) {
      return {""};
    }
    if (n == 1) {
      return {"()"};
    }
    std::vector<string> ret;
    for (int na = 0; na < n; na++) {
      int nb = n - na - 1;
      auto a = generateParenthesis(na);
      auto b = generateParenthesis(nb);
      for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
          ret.push_back("(" + a[i] + ")" + b[j]);
        }
      }
    }
    return ret;
  }
};