LeetCode | 22.括号生成

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

方案一：递归

  当有 n 对括号时，字符串的长度为 2n。此时可以插入的 '(' 数量为 n, 可以插入的 ')' 数量为 0 (要有对应的左括号才可以插入右括号，否则就是非法的)。

开始递归：

• 插入一个左括号后，可插入的左括号数量减一，可插入的右括号数量加一
• 插入一个右括号后，可插入的右括号数量减一
• 退出条件：当可插入的左右括号数量都为 0 时，退出递归

vector<string> generateParenthesis(int n) {
    vector<string> res;
    string tmp = "";
    helper(res, tmp, n, 0);
    return res;
}

void helper(vector<string>& res, string& tmp, int l, int r) {
    if (l == 0 && r == 0) {
        res.push_back(tmp);
        return;
    }
    if (l > 0) {
        tmp.push_back('(');
        helper(res, tmp, l - 1, r + 1);
        tmp.pop_back();
    }
    if (r > 0) {
        tmp.push_back(')');
        helper(res, tmp, l , r - 1);
        tmp.pop_back();
    }
}

方案二：动态规划

  设 dp[i] 包含长度为 2*i 的所有有效括号组合。
  假设你已经得到了dp[2]，它是{(())，()()}。那么dp[3]将是什么呢？可以写成以下形式：

( + dp[0] + ) + dp[2] = ()(()) 和 ()()()
( + dp[1] + ) + dp[1] = (())()
( + dp[2] + ) + dp[0] = ((())) 和 (())()

因此，可以看到，这个问题具有重叠子问题的结构。

dp[i] = "(" + dp[j] + ")" + dp[i-j-1]

注意： dp[j] 和 dp[i - j - 1] 都包含多个字符串，要遍历出所有可能的情况

vector<string> generateParenthesis(int n) {
    vector<vector<string>> dp(n + 1);
    dp[0] = {""};
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            vector<string> left = dp[j];
            vector<string> right = dp[i - j - 1];
            for (int l = 0; l < left.size(); ++l) {
                for (int r = 0; r < right.size(); ++r) {
                    dp[i].push_back("(" + left[l] + ")" + right[r]);
                }
            }
        }
    }
    return dp[n];
}