LeetCode 面试题 08.09. 括号
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
文章目录
一、题目
括号。设计一种算法打印n对括号的所有合法的例如开闭一一对应组合。
说明解集不能包含重复的子集。
例如给出 n = 3生成结果为
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
二、C# 题解
题目比较简单代码如下。
public class Solution {
public IList<string> GenerateParenthesis(int n) {
IList<string> ans = new List<string>();
Partition(ans, new StringBuilder(), 0, 0, n);
return ans;
}
public void Partition(IList<string> ans, StringBuilder sb, int i, int j, int n) {
if (i == n && j == n) { // 递归出口
ans.Add(sb.ToString());
return;
}
if (i == n) { // 左括号添加完只能添加右括号
sb.Append(')');
Partition(ans, sb, i, j + 1, n);
sb.Remove(sb.Length - 1, 1); // 回溯
}
else { // 左、右括号都可以继续添加
// 先添加左括号
sb.Append('(');
Partition(ans, sb, i + 1, j, n);
sb.Remove(sb.Length - 1, 1); // 回溯
// 如果可以添加右括号则添加
if (i > j) {
sb.Append(')');
Partition(ans, sb, i, j + 1, n);
sb.Remove(sb.Length - 1, 1); // 回溯
}
}
}
}
- 时间128 ms击败 100.00% 使用 C# 的用户
- 内存43.50 MB击败 83.33% 使用 C# 的用户
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |