Leetcode Index

22.Generate Parentheses

22.Generate Parentheses

难度:Medium

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

例如,给出 n = 3,生成结果为:

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

动态规划,可以将已有的有效括号分成左右两部分有效括号,然后在左右分别插入左右括号。这样可以生成下一个长度的有效括号对。

class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
if(n ==0) res.push_back("");
else
{
for(int i=0;i<n;i++)
for(auto left: generateParenthesis(i))
for(auto right: generateParenthesis(n-i-1))
res.push_back( '(' +left+ ')' + right );
}
return res;
}
};

执行用时 :12 ms, 在所有 C++ 提交中击败了60.89%的用户 内存消耗 :15.4 MB, 在所有 C++ 提交中击败了84.63%的用户