problem:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
一想到要用递归来解决的就有点头疼,因为还没有好好系统的回顾一下递归,总觉得判断什么时候返回很困难。这个是这样的,用l和r分别记录剩下的左括号和右括号。当l和r都为零的时候就是输出了一种正确的可能了。前提是任何时刻,剩下的右括号要比左括号多或者相等,否则返回。其次,r和l都为零的时候,就把temp str记录下来。代码和部分注释如下:
class Solution {
private:
void subGe(int l, int r, string t, vector<string> &ans)
{
if(l > r) // 左代表‘(’右代表‘)’,剩下的左括号要比右括号少才合法
return ;
if (l == && r == )
{ans.push_back(t);return;} // 这是t已经是2n个字符了
if(l > )
subGe(l - , r, t + "(", ans); // 输出一个(,则左括号减一
if(r > )
subGe(l, r - , t + ")", ans);
}
public:
vector<string> generateParenthesis(int n)
{
vector<string> ans;
ans.clear();
if (n <= )
return ans;
subGe(n, n, "", ans);// 初始时,左右括号都是n个
return ans;
}
};