首页 > 代码库 > leetcode -- medium part
leetcode -- medium part
22. Generate Parentheses
1 class Solution 2 { 3 private: 4 void generateParenthesis(vector<string> &v, string s, int l, int r) // l和r记录剩余左右括号的数量 5 { 6 if(l == 0 && r == 0) // 当且仅当左右括号数量都为0时,正常结束 7 v.push_back(s); 8 9 if(l > 0) 10 generateParenthesis(v, s + "(", l - 1, r); 11 if(r > 0 && l < r) // 剩余的右括号数量比左括号多时才能添加右括号 12 generateParenthesis(v, s + ")", l, r - 1); 13 } 14 public: 15 vector<string> generateParenthesis(int n) 16 { 17 vector<string> v; 18 generateParenthesis(v, "", n, n); 19 return v; 20 } 21 };
括号匹配数是一个卡特兰数,f(x) = (2n)!/((n+1)! * n!) , f(3) = 5
当作dfs处理,这样得到的顺序是"("从多到少的顺序。
leetcode -- medium part
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。