凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 22. Generate Parentheses

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


题目

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

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

题意

给出 n 组括号的所有合法的组合情况。

解法 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, vector<string>());
        dp[0].push_back("");
        for(int i=1; i<=n; ++i){
            for(int k=0; k<i; ++k){
                for(string s1: dp[k]){
                    for(string s2: dp[i-1-k])
                        dp[i].push_back("("+s2+")"+s1);
                }
            }
        }

        return dp[n];
    }
};