题解 | #括号生成#

思路：

相当于一共�n个左括号和�n个右括号，可以给我们使用，我们需要依次组装这些括号。每当我们使用一个左括号之后，就剩下�−1n−1个左括号和�n个右括号给我们使用，结果拼在使用的左括号之后就行了，因此后者就是一个子问题，可以使用递归：

• 终止条件： 左右括号都使用了n个，将结果加入数组。
• 返回值： 每一级向上一级返回后续组装后的字符串，即子问题中搭配出来的括号序列。
• 本级任务： 每一级就是保证左括号还有剩余的情况下，使用一次左括号进入子问题，或者右括号还有剩余且右括号使用次数少于左括号的情况下使用一次右括号进入子问题。

但是这样递归不能保证括号一定合法，我们需要保证左括号出现的次数比右括号多时我们再使用右括号就一定能保证括号合法了，因此每次需要检查左括号和右括号的使用次数。

具体做法：

• step 1：将空串与左右括号各自使用了0个送入递归。
• step 2：若是左右括号都使用了�n个，此时就是一种结果。
• step 3：若是左括号数没有到达�n个，可以考虑增加左括号，或者右括号数没有到达�n个且左括号的使用次数多于右括号就可以增加右括号。

#include <vector>
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    void recursion(int left,int right,string temp,vector<string> &res,int n)
    {
        //左右括号都用完了，就加入结果
        if(left == n && right == n)
        {
            res.push_back(temp);
            return;
        }
        //使用一次左括号
        if(left < n)
            recursion(left+1, right, temp + '(',res, n);
        //使用一次右括号，右括号个数必须少于左括号
        if(right < n && left > right)
            recursion(left, right+1, temp+')', res, n);
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        vector<string> res;//记录结果
        string temp;//记录每次组装的字符串
        //递归求结果
        recursion(0, 0, temp, res, n);
        return res;
    }
};