学步园

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

思路：

左右括号总数相同，且在填充时左括号的个数始终要大于等于右括号的个数。据此递归生成所有的括号对。

题解：

class Solution {
public:
    vector<string> result;
    
    void generate_string(const string str, int lpnum, int rpnum)
    {
        if (lpnum == 0 && rpnum == 0)
        {
            result.push_back(str);
            return;
        }
        
        if (lpnum > 0)
            generate_string(str + '(', lpnum - 1, rpnum);
        
        if (rpnum > lpnum)
            generate_string(str + ')', lpnum, rpnum - 1);
    }
    
    vector<string> generateParenthesis(int n) {
        result.clear();
        
        generate_string("", n, n);
        
        return result;
    }
};