1、思路

生成n对匹配的括号需要满足以下两个条件：

• 左括号或右括号的数目不能超过n个；

• 右括号的个数始终不能超过左括号，否则会出现诸如“())”这样的不匹配括号。

2、代码

class Solution {
public:
    //参数left与right分别表示左右括号当前还需要插入的数量
    void dfs(vector<string>& res, int left, int right, string tmp)
    {
        if (left == 0 && right == 0)
        {
            res.push_back(tmp);
            return;
        }

        if (left > 0)
        {
            //tmp不要传引用，因为对于 tmp + "(" 是不能取地址的
            dfs(res, left - 1, right, tmp + "(");
        }

        if (left < right)       //满足条件2
        {
            dfs(res, left, right - 1, tmp + ")");
        }
    }

    vector<string> generateParenthesis(int n) {
        vector<string> res;

        dfs(res, n, n, "");

        return res;
    }
};