22. 括号生成*

[MyLinChi]

题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方案一（回溯法）

序列的左括号数不能小于右括号数，并且左括号数不能大于n。

class Solution {
public:
    int n;
    vector<string> res;
    void genDFS(string path,int level,int ln,int rn){
        if(ln<rn)return;
        if(ln>n)return;
        if(level==n*2){
            res.push_back(path);
            return;
        }
        genDFS(path+"(",level+1,ln+1,rn);
        genDFS(path+")",level+1,ln,rn+1);
    }
    vector<string> generateParenthesis(int n) {
        this->n = n;
        res = {};
        genDFS("",0,0,0);
        return res;
    }
};

方案二（分治）

任意一个合法序列都可以表示成
（左部）右部
的形式。如："(())()()"的左部就是"()"，右部就是"()()"。因此只需要枚举左部的括号对数，然后把问题分成生成左部序列和右部序列。最后合并的时候就是两个事件的组合问题了。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res = {};
        if(n==0)res.push_back("");
        else
        for(int i=0;i<n;i++){
            vector<string> Left = generateParenthesis(i);
            for(int j=0;j<Left.size();j++){
                vector<string> Right = generateParenthesis(n-i-1);
                for(int k = 0;k<Right.size();k++)
                    res.push_back("("+Left[j]+")"+Right[k]);
            }
        }
        return res;
    }
};

方案三（动态规划）

合法序列的表示与方案二类似，只是用了动态规划的方法，保存每一步的结果到一个vector<vector>类型的变量m中，注意m的外层vector大小声明和前几个元素的初始化。

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		if (n == 0)return{};
		if (n == 1)return{ "()" };
		vector<string> res = {};
		vector<vector<string>> m(n+1);
		m[0] = {""};
		m[1] = {"()"};
		for (int i = 2; i <= n; i++){
			for (int j = 0; j<i; j++){
				for (string p : m[j]){
					for (string q : m[i - j - 1])
						m[i].push_back("(" + p + ")" + q);
				}
			}
		}
		return m[n];
	}
};