22. Generate Parentheses.md

22. Generate Parentheses

思路

给定括号的个数，返回所有可能的合法的括号组成情况。

思路一

用str代表一个合法的括号串，初始为空。再作如下定义:

• 用left代表当前还能往str加入左括号的个数，left初始为n；
• 用right代表当前还能往str加入右括号的个数，right初始为0（即str不能以右括号开头）。

定义一个递归函数helper:

• 递归出口：当left和right都等于0，此时str就应该是一个合法的括号串，push进结果数组中再返回即可。
• 否则，若right > 0, 说明此时可以添加右括号了，right应该减一，进入递归，跳出递归后，若left > 0，则添加左括号，left减一right加一。

思路二

其实和思路一类似，不过亲测要比思路一快一些。
用str代表一个括号字符串，初始为空。再作如下定义:

• left代表使str成为含有n个括号的合法串还应该向str中加入的左括号的个数（即若当前str中左括号的个数为k，则left=n-k），left初始为n；
• right定义同理，right初始也为n。（注意和思路一不一样）

有了以上定义，那么当left > right时，说明str中左括号数小于右括号数，例如"())"，则str不合法。
定义一个递归函数helper:

• 递归出口：left > right时直接return，或者当left和right都等于0，此时str就应该是一个合法的括号串，push进结果数组中再返回即可。
• 否则，若right > 0, 说明此时可以添加右括号了，right应该减一，进入递归，跳出递归后，若left > 0，则添加左括号，left减一（与思路一不同:right不加一）。

思路一

class Solution {
private:
    void helper(vector<string> &res, string str, int left, int right){
        // left代表此时还能添加的左括号的个数，right代表此时能添加上的右括号的个数
        if(left == 0 && right == 0){
            res.push_back(str);
            return;
        }
        if(right > 0) helper(res, str + ")", left, right - 1);  
        if(left > 0) helper(res, str + "(", left - 1, right + 1); // 添加一个左括号后就可以多添加一个右括号了
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string>res;
        helper(res, "", n, 0); // 不能一开始就添加右括号，所以right=0
        return res;
    }
};

思路二

与思路一不同的只有三个地方，下面标了出来

class Solution {
private:
    void helper(vector<string> &res, string str, int left, int right){
        // left代表使str成为含有n个括号的合法串还应该向str中加入的左括号的个数，right同理
        if(left > right) return; // 不同点1
        if(left == 0 && right == 0){
            res.push_back(str);
            return;
        }
        if(right > 0) helper(res, str + ")", left, right - 1);  
        if(left > 0) helper(res, str + "(", left - 1, right);  // 不同点2
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string>res;
        helper(res, "", n, n); // 不同点3
        return res;
    }
};