LeetCode 22. 括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

思路解析

生成(n)对括号的几何(S(n))，有以下递推关系：

[S(n) = sum_{i = 0}^n( LeftParentheses + S(n - i - 1) + RightParentheses + S(i)) ]

代码实现

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