LeetCode LCR 085.括号生成

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

示例 1：

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：

输入：n = 1
输出：[“()”]

提示：

1 <= n <= 8

法一：直接生成由’(‘和’)'组成的全部可能的字符串，然后再一个一个判断是否合法：

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> res;string s(2 * n, '\0');getAllParentheses(res, 0, s, n);return res;}private:void getAllParentheses(vector<string> &res, int index, string &s, int n){if (index == 2 * n){if (isValid(s)){res.push_back(s);}return;}s[index] = '(';getAllParentheses(res, index + 1, s, n);s[index] = ')';getAllParentheses(res, index + 1, s, n);}bool isValid(string &s){int cnt = 0;for (char c : s){if (c == '('){++cnt;}else{--cnt;}if (cnt < 0){return false;}}return cnt == 0;}
};

此方法时间复杂度为O(n2${}^{2n}$)；空间复杂度为O(n)，最多递归2n层。很差的方法。

法二：递归求解即可：

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> res;int leftParenthesisNum = 0;string s(2 * n, '0');getParentheses(res, 0, 0, 0, s, n);return res;}private:void getParentheses(vector<string> &res, int leftNumAll,int finishNum, int index, string &s,int n){if (index == 2 * n){res.push_back(s);}if (leftNumAll < n){s[index] = '(';getParentheses(res, leftNumAll + 1, finishNum, index + 1, s, n);}if (finishNum < leftNumAll){s[index] = ')';getParentheses(res, leftNumAll, finishNum + 1, index + 1, s, n);}}
};

法三：我们可以把生成的结果看做(a)b，其中a和b分别是合法括号串。我们枚举每个右括号，分别计算枚举过程中a和b的内容，并且可以把特定长度的a和b的内容缓存下来：

class Solution {
public:vector<string> generateParenthesis(int n) {vector<vector<string>> cache(9);cache[0] = {""};return generate(n, cache);}private:vector<string> generate(int n, vector<vector<string>> &cache){if (cache[n].size() != 0){return cache[n];}vector<string> cur;for (int i = 0; i < n; ++i){vector<string> left = generate(i, cache);vector<string> right = generate(n - 1 - i, cache);for (string &sleft : left){for (string &sright : right){cur.push_back("(" + sleft + ")" + sright);}}cache[n] = cur;}return cache[n];}
};