from CodeTop, Leetcode, 22. 括号生成。
建议背过。
题意：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]示例 2：
输入：n = 1
输出：[”()”]
解读：
显然要用递归去做。明确三个要点：
- 初始括号左右数量为零，当且仅当左右括号数量都为 n 的时候，将当前括号组合加入到答案，并退出。
- 当且仅当序列中左括号数量小于 n 的时候，可以继续加入左括号。
- 当且仅当序列中右括号数量小于左括号的时候，可以继续加入右括号。
代码：
vector<string> ans;
vector<string> generateParentthesis(int n){
dfs(n, 0, 0, "");
return ans;
}
void dfs(int n, int lc, int rc, string seq){
if (lc == n && rc == n){
ans.emplace_back(seq);
return ;
}
if (lc < n) dfs(n, lc+1, rc, seq + '(');
if (rc< lc) dfs(n, lc, rc+1, seq + ')');
}
