Leetcode: Generate Parentheses
Leetcode: Generate Parentheses
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 15:13:24
发布于 2019-01-22 15:13:24
题目： 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:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”
思路分析： 最后的组合结果总有这样的规律：左括号的个数大于等于右括号的个数。所以，按照这个规律：假设在位置k剩余left个左括号和right个右括号，如果left>0，可以直接打印左括号。，如果left<right且right!=0，则可以打印右括号。如果left和right均为零，则说明已经完成一个合法排列，可以将其打印出来。
C++参考代码：
class Solution
{
private:
void generateSub(vector<string> &result, string current, int left, int right)
{
if (left == 0 && right == 0) result.push_back(current);
else
{
if (left != 0) generateSub(result, current + '(', left - 1, right);
if (left < right && right != 0) generateSub(result, current + ')', left, right - 1);
}
}
public:
vector<string> generateParenthesis(int n)
{
vector<string> result;
if (n > 0) generateSub(result, string(), n, n);
return result;
}
};C#参考代码：
public class Solution
{
private void GenerateSubString(IList<string> result, string current, int left, int right)
{
String value = current;
if (left == 0 && right == 0) result.Add(value);
else
{
if (left != 0) GenerateSubString(result, current + '(', left - 1, right);
if (left < right && right != 0) GenerateSubString(result, current + ')', left, right - 1);
}
}
public IList<string> GenerateParenthesis(int n)
{
IList<string> result = new List<string>();
if (n > 0) GenerateSubString(result, "", n, n);
return result;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年04月13日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读