算法39 leetcode22. 括号生成

开始的想法

生成n个独立的(),然后把最后一个往前面扔（重复这个过程）
但是不好实现

答案解法思路是类似生成然后去除不符合的项

用动规好理解一些

n+1可以理解为比n项多了一个括号，所以把n项放在括号里面p项和外面q项排列；p和q就转化成了子问题。但是要注意p和q的顺序是固定的，可以是p(q)、(p)q，但是为了保持不对称来避免重复项不能是pq()、()pq

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<vector<string>> brc;
        brc.push_back({""});
        brc.push_back({"()"});
        for(int i=2;i<=n;i++){
            vector<string> t;
            //利用n-1组合拼出n

            for(int a=0;a<i;a++){//a+b=n-1（p+q=n-1）
                int b=i-1-a;
                vector<string> p(brc[a]);
                vector<string> q(brc[b]);
                for( auto ps:p){
                    for( auto qs:q){
                        string ss="(";
                        ss=ss+ps+")"+qs;//(p)+q
                        t.emplace_back(ss);
                    }   
                }
            }
            brc.push_back(t);
        }
        return brc[n];    
    }
    
};