LeetCode 面试题 08.09. 括号

一、题目

  括号。设计一种算法，打印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); // 回溯
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• 时间：128 ms，击败 100.00% 使用 C# 的用户
• 内存：43.50 MB，击败 83.33% 使用 C# 的用户