22. 括号生成

    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
    }