题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n =_ _3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题解

暴力法

参考自官方。

暴力法的难点在于判断暴力生成的序列组合是否有效。其实方法很简单，从左往右统计左括号和右括号的数量，只要左括号数量一直大于等于右括号数量，并最终左括号数量等于右括号数量即可。

private static bool Valid(char[] current)
{
    var balance = 0;
    foreach (var c in current)
    {
        if (c == '(') balance++;
        else balance--;
        if (balance < 0) return false;
    }
    return balance == 0;
}

暴力法完整代码：

public static IList<string> GenerateParenthesis(int n)
{
    var combinations = new List<string>();
    GenerateAll(new char[2 * n], 0, combinations);
    return combinations;
}
private static void GenerateAll(char[] current, int pos, List<string> res)
{
    if (pos == current.Length)
    {
        if (IsValid(current)) res.Add(new string(current));
    }
    else
    {
        current[pos] = '(';
        GenerateAll(current, pos + 1, res);
        current[pos] = ')';
        GenerateAll(current, pos + 1, res);
    }
}
private static bool IsValid(char[] current)
{
    var balance = 0;
    foreach (var c in current)
    {
        if (c == '(') balance++;
        else balance--;
        if (balance < 0) return false;
    }
    return balance == 0;
}

回溯法

大体思路和暴力法类似，只是仅在序列依然有效时才添加 ‘(‘ 或 ‘)’。

• 只要左括号数量小于 n，就能拼接一个左括号

• 只要右括号数量小于左括号数量，就能拼接一个右括号

public static IList<string> GenerateParenthesis(int n)
{
    var res = new List<string>();
    Backtrack(res, "", 0, 0, n);
    return res;
}
private static void Backtrack(ICollection<string> res, string current, int open, int close, int max)
{
    if (current.Length == 2 * max)
    {
        res.Add(current);
        return;
    }
    if (open < max) Backtrack(res, current + "(", open + 1, close, max);
    if (close < open) Backtrack(res, current + ")", open, close + 1, max);
}