leetcode 22括号生成
程序员文章站
2022-05-20 11:42:33
...
题目
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
分析
- 使用回溯算法进行DFS,路径的每个节点都有2个选择, ‘(’ or ‘)’
- 终止条件: 路径上’)'的个数right 大于 '('的个数left
(right > left,即右括号比左括号多,一定不会出现匹配)
or '('的个数left 大于 n(left > n)
- 解的判断条件:
left == right && left == n
code
class Solution {
public:
vector<string> result;
void backtrace(string& tmp,int l,int r,int n){
if(r > l || l > n) return;
if(l == r && l == n){
result.push_back(tmp);
return ;
}
tmp.push_back('(');
backtrace(tmp,l+1,r,n);
*tmp.rbegin() = ')'; // 把pop_back()与push_back()合在一起
backtrace(tmp,l,r+1,n);
tmp.pop_back();
}
vector<string> generateParenthesis(int n) {
string tmp;
backtrace(tmp,0,0,n);
return result;
}
};
下一篇: 拦截导弹(动态规划)
推荐阅读
-
leetcode 921. 使括号有效的最少添加(Python)
-
5、有效的括号-Python-LeetCode-20
-
leetcode - 括号字符串是否有效
-
LeetCode——有效的括号(括号匹配)
-
[题记]有效括号的嵌套深度-leetcode
-
荐 【小白用python刷Leetcode】32. 最长有效括号
-
LeetCode-32.Longest Valid Parentheses最长有效括号子串
-
括号相关题目 LeetCode 20 有效括号 LeetCode 32 最长有效括号子串
-
Longest Valid Parentheses leetcode java (求最长有效匹配括号子串的长度)-动态规划
-
C++ LeetCode 22 括号生成