凌云的博客

LeetCode 算法题 22. 括号生成

分类：algorithm| 发布时间：2016-07-07 11:18:00

---

题目

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

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

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

解法 DFS

使用递归可以很容易实现

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        addparenthesis(res, "", n, 0);
        return res;
    }

    void addparenthesis(vector<string> &v, string str, int n, int m){
        if (n == 0 && m == 0) {
            v.push_back(str);
            return;
        }

        if (n > 0) { addparenthesis(v, str+"(", n-1, m+1); }
        if (m > 0) { addparenthesis(v, str+")", n, m-1); }
    }
};

解法 DP

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<vector<string>> dp(n+1);
        dp[0].push_back("");
        for(int i=1; i<=n; ++i){
            for(int k=0; k<i; ++k){
                for(const string& s1: dp[k]){
                    for(const string& s2: dp[i-1-k])
                        dp[i].push_back("("+s2+")"+s1);
                }
            }
        }

        return dp[n];
    }
};