原题描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例
代码语言：javascript复制输入：n = 3
输出：["((()))",
"(()())",
"(())()",
"()(())",
"()()()" ]原题链接：https://leetcode-cn.com/problems/generate-parentheses
思路解析
这竟然是一道简单题，并且通过率有75.5%。其实很容易想到是递归的思路，问题是有的人在寻找递推关系的路上越走越偏。
一个常见的错误思路是：f(n)可以拆分成f(1)拼接f(n-1), f(2)拼接f(n-2).....这种方法包含了大量的重复答案。比如n=3时，f(1)拼接f(n-1)和f(n-1)拼接f(1)都会产生'()()()'的结果，所以这个递推关系要再修改一下。
任何一个合理的序列都会以'('开头，并且肯定有一个')'与其对应，在这对括号之间既可能有合法的子括号序列，也可能什么都不存在。所以在这对括号内可以放一个子问题。所以，一种合理的递推关系是f(n)=(f(i))f(n-i)，这种情况不会有重复答案。
复杂度分析
- 时间和空间复杂度确实比较难求，这道题不强求。
C 参考代码
代码语言：javascript复制
class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0) return {""};
vector<string> res;
for (int i = 0; i < n; i) {
vector<string> left = generateParenthesis(i);
vector<string> right = generateParenthesis(n - i - 1);
for (string a: left) {
for (string b: right) {
string cat_str = "(" a ")" b;
res.push_back(cat_str);
}
}
}
return res;
}
};
