022.md

Generate Parentheses

题目：

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:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路：

要使括号合理，一个规律 右括号的出现条件是：右括号的数量小于左括号的数量。

而左括号出现的条件是：只要左括号的数量大于0就可以了，也就是说当 左括号数量小于右括号数量的时候，下一个有可能是左或者右括号。

这就是一个递归算法，不断的满足各自的条件生成下一个括号。

特点就是 在每个时刻总要满足一个条件 左括号出现的次数大于等于有括号的次数。

代码：

class Solution {
public:
    void generate_parenthesis(int left,int right,string str,vector<string> &re)
    {
        if(left==0 && right==0){
            re.push_back(str);
        }
        
        if(left>0){
            generate_parenthesis(left-1,right,str+'(',re);
        }
        
        if(right>left){
            generate_parenthesis(left,right-1,str+')',re);
        }
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> re;
        string temp;
        generate_parenthesis(n,n,temp,re);
        return re;
    }
};