题目描述

给定 括号对数 n ，生成所有有效括号对

样例

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

(动态规划) $O(n^2)$

”“
“()”
$ () \color{Red}{()} ,(\color{Red}{()}) $
$ () \color{Red}{()()}, () \color{Red}{(())},(\color{Red}{()})\color{Red}{()}, (\color{Red}{()()}), (\color{Red}{(())})$

由上面可以推导递推公式

$dp[n] = “(” + strA + “)” + strB$

由递推公式可知 $strA$ 和 $strB$ 的括号对数和为 n - 1

其中
$strA$ 是 $j$ 对括号, $j \in [0,n - 1]$
$strB$ 是 $n - j - 1$ 对括号

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<vector<string>> v(n + 1);
        v[0].push_back("");//0对括号
        for (int i = 1; i <= n; i ++ ) {
            for (int j = 0; j < i; j ++ ) {
                for (auto& str1 : v[j]) {
                    for (auto& str2 : v[i - j - 1]) {
                        v[i].push_back("(" + str1 + ")" + str2);
                    }
                }
            }
        }
        return v[n];
    }
};