leetcode第21题--Generate Parentheses

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;

 }

};

巴特西

leetcode第21题--Generate Parentheses

最新文章

热门文章