22.md

title	date
22. 括号生成	2020-03-17T22:59:00.000Z

力扣

错误解法：

    func generateParenthesis(n int) []string {
        var res []string
        if n < 1 {
            return res
        }
        if n == 1 {
            res = append(res, "()")
            return res
        }
        temps := generateParenthesis(n-1)
        for _, item := range temps {
            a := "(" + item + ")"
            res = append(res, a)
            b := "()" + item
            if a != b {
                res = append(res, b)
            }
            c := item + "()"
            if a!=c && b!=c {
                res = append(res, c)
            }
        }
        return res
    }

使用递归的方式，基于上一次构建的结果，增加新括号。

这个解法的问题在于，上一次构建的结果一定是已经符合条件的结果，因此会漏掉那些在上一次构建中不符合条件，但是在下一次构建中，可能会达成符合条件的结果的情况。

正确解法：

    func generateParenthesis(n int) []string {
        return generator(n, 0, "")
    }
    
    func generator(left, right int, s string) (res []string) {
        if left == 0 && right == 0 {
            res = append(res, s)
            return
        }
        if left > 0 {
            res = generator(left - 1, right + 1, s + "(")
        }
        if right > 0 {
            res = append(res, generator(left, right - 1, s + ")")...)
        }
    
        return res
    }

一个 "(" 一定与一个 ")" 一一对应。基于此原则，我们要计算 n 对括号，就一定有 n 个 "(" 和 n 个 ")"。我们将 n 个 "(" 与 n 个 ")" 进行排列组合能够拿到一系列字符串，但这里的排列组合有一些特别的规则：

1. 一个 "(" 对应一个 ")"。因此每增加一个 "("，"(" 的待使用量就减少 1，")" 的待使用量就增加 1
2. 第一个字符一定是 "("。因此我们从 "(" 开始迭代，每个 "(" 的下一个字符，可能是 "("，也可能是 ")"，需要基于各自剩余的待使用量来确定。

通过分析问题，我们发现，要找到 n 对括号的有效组合，其实就是找 "(" 后面的括号的排列方式。因为有两种可能，所以就需要把两种都算一遍。