解决方案:
利用递归的思想,逐步添加括号,
1)生成括号的规则:只有左括号的数量大于右括号的时候,才能添加右括号;
2)停止条件:当左右括号的数量相等,总的括号对数等于n时,停止递归;
//用递归来生成括号
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result; //保存最后生成的括号对
generate(n, n, 0, "", result); //生成括号序列
return result;
}
//n为括号的对数,left为可以添加的左括号的个数,right是能够添加的有括号的个数,result为最终的结果
void generate(int n, int left, int right, string item, vector<string> &result)
{
if(left == 0 && right == 0) //如果左右括号都已经添加完成,则将括号序列保存到result中去
{
result.push_back(item);
return;
}
if(left > 0) //如果left大于0,说明可以添加左括号
generate(n, left - 1, right + 1, item + "(", result); //right+1是因为只有添加了左括号才能添加有括号
if(right > 0) //如果right大于0,说明可以添加右括号
generate(n, left, right - 1, item + ")", result);
}
};