目录
力扣22. 括号生成
难度 中等
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
class Solution {
public:
vector<string> generateParenthesis(int n) {
}
};解析代码
从左往右进行递归，在每个位置判断放置左右括号的可能性，若此时放置左括号合理，则放置左括号继续进行递归，右括号同理。
一种判断括号是否合法的方法：从左往右遍历，左括号的数量始终大于等于右括号的数量，并且左括号的总数量与右括号的总数量相等。因此我们在递归时需要进行以下判断：
- 放入左括号时需判断此时左括号数量是否小于字符串总长度的一半（若左括号的数量大于等于字符串长度的一半时继续放置左括号，则左括号的总数量一定大于右括号的总数量）
- 放入右括号时需判断此时右括号数量是否小于左括号数量
定义两个全局变量 left 和 right 分别记录左括号和右括号的数，还有常用的string path;和vector<string> ret;，递归流程如下：
- 递归结束条件：当前状态字符串长度与 2*n 相等，记录当前状态并返回
- 若此时左括号数量小于字符串总长度的一半，则在当前状态的字符串末尾添加左括号并继续递归， 递归结束撤销添加操作
- 若此时右括号数量小于左括号数量，则在当前状态的字符串末尾添加右括号并递归，递归结束撤销添加操作
class Solution {
int left, right, _n;
string path;
vector<string> ret;
public:
vector<string> generateParenthesis(int n) {
_n = n;
dfs();
return ret;
}
void dfs()
{
if(right == _n)
{
ret.push_back(path);
return;
}
if(left < _n) // 添加左括号
{
path += '(';
++left;
dfs();
path.pop_back(); // 恢复现场
--left;
}
if(right < left) // 添加右括号
{
path += ')';
++right;
dfs();
path.pop_back(); // 恢复现场
--right;
}
}
};
