题解 | #括号生成#

方法：递归 + 回溯

首先我们可以把问题当成n个左括号和n个右括号的排列问题。那么要保证排列是正确的，只要保证排列时：1、第一个元素为左括号；2、排列时，使用右括号需要保证此时字符串中的左括号比右括号多。

根据上面两个特性，可以使用递归来进行解答。

具体做法：

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

时间复杂度：

空间复杂度：o(n)。

class Solution {
  public:
    vector<string> generateParenthesis(int n) {
	  	//特殊情况处理
        if (n == 0)
            return res;

        string temp;

        generate(0, 0, n, temp);
        return res;
    }

  private:
    vector<string> res;

    void generate(int left, int right, int n, string temp) {
	  	//当左括号和右括号都使用完了，加入结果
        if (left == n && right == n) {
            res.push_back(temp);
            return;
        } else {
		  	//使用左括号
            if (left < n) {
                generate(left + 1, right, n, temp + '(');
            }
		  	//添加右括号需要保证左括号使用的次数比右括号多
            if (right < n && left > right) {
                generate(left, right + 1, n, temp + ')');
            }
        }
    }

};