Powered By GitBook
22.Generate Parentheses

22.Generate Parentheses

难度:Medium
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
1
[
2
"((()))",
3
"(()())",
4
"(())()",
5
"()(())",
6
"()()()"
7
]
Copied!
动态规划,可以将已有的有效括号分成左右两部分有效括号,然后在左右分别插入左右括号。这样可以生成下一个长度的有效括号对。
1
class Solution {
2
public:
3
vector<string> generateParenthesis(int n) {
4
vector<string> res;
5
if(n ==0) res.push_back("");
6
else
7
{
8
for(int i=0;i<n;i++)
9
for(auto left: generateParenthesis(i))
10
for(auto right: generateParenthesis(n-i-1))
11
res.push_back( '(' +left+ ')' + right );
12
}
13
return res;
14
}
15
};
Copied!
执行用时 :12 ms, 在所有 C++ 提交中击败了60.89%的用户 内存消耗 :15.4 MB, 在所有 C++ 提交中击败了84.63%的用户
Last modified 2yr ago
Copy link