首页 > 代码库 > Leetcode: Generate Parentheses
Leetcode: Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
分析：这里介绍两种方法，一种是递归构造法，另一种是dfs。
1. 递归法
这种方法简单明了，但要理解是如何构造的，n对有效括号对，可以通过i(0=< i <= n-1)对有效括号对inner和n-1-i对有效括号对outer构造，"("+inner+")"+outer, 且无重复。
class Solution {public: vector<string> generateParenthesis(int n) { if(n == 0) return vector<string>(1,""); if(n == 1) return vector<string>(1,"()"); vector<string> result; for(int i = 0; i < n; i++){ for(auto inner : generateParenthesis(i)) for(auto outer : generateParenthesis(n-1-i)) result.push_back("("+ inner + ")" + outer); } return result; }};
2. 还可以用dfs求解，在生成的过程中始终保证"("的个数大于等于")"的个数。
class Solution {public: vector<string> generateParenthesis(int n) { vector<string> result; if (n > 0) generate(n, "", 0, 0, result); return result; } void generate(int n, string s, int l, int r, vector<string> &result) { if (l == n) { result.push_back(s.append(n - r, ‘)‘)); return; } generate(n, s + ‘(‘, l + 1, r, result); if (l > r) generate(n, s + ")", l, r + 1, result); }};
Leetcode: Generate Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。