题解 | #括号生成#

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> s;
    //该递归函数的含义为从start到end上每个位置都可以填（ 或者 ）返回所有的合法可能
    //其中count变量是用来判断当前方案是否合法
    //该函数不但实现了题目要求还有副产物就是总的方法数即res
    int process(int start,int end,int count,string str)
    {
        if(start>end)
            return 0;
        if(count<0)
            return 0;
        if(start==end){
            if(count==1){
                str+=')';
                s.push_back(str);
                count--;
                return 1;//返回1表示找到了一种可行方案
            }
            else if(count==-1){
                str+='(';
                s.push_back(str);
                count++;
                return 1;
            }
            else return 0;
        }
        int res=0;
        //如果当前位置填（
        res+=process(start+1, end, count+1, str+'(');
        //如果当前位置填）
        res+=process(start+1, end, count-1, str+')');
        return res;
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        process(1, 2*n, 0,"");
        return s;
    }
};