括号生成

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

解题思路：
1.深度优先遍历
  首先假设无限个括号，第一个只能是左括号，第二个就可以在左括号和右括号里面选，这样很像一棵二叉树，然后深度优先遍历，过程中保证左括号数量不大于n，同时不小于右括号数量。

func generateParenthesis(n int) []string {
    var recursive func(l, r int, s string)
    ret := []string{}
    recursive = func(l, r int, s string) {
        if 0 == l && 0 == r {
            ret = append(ret, s)
            return
        }

        if l != 0 {
            recursive(l-1, r, s+"(")
        }

        if l < r {
            recursive(l, r-1, s+")")
        }
    }
    recursive(n, n, "")
    return ret
}

2.暴力法
  和上一个方法相似，但是遍历过程中不保证左括号数量不小于右括号数量，结束后需要对结果进行筛选，剔除不符合规则的括号。

func generateParenthesis(n int) []string {
    var recursive func(l, r int, s string)
    tmp := []string{}
    recursive = func(l, r int, s string) {
        if 0 == l && 0 == r {
            tmp = append(tmp, s)
            return
        }
        if 0 < l {
            recursive(l-1, r, s+"(")
        }
        if 0 < r {
            recursive(l, r-1, s+")")
        }

    }
    recursive(n, n, "")

    g := func(s string) bool {
        i := 0
        for _, val := range s {
            if '(' == val {
                i++
            } else {
                i--
            }
            if i < 0 {
                return false
            }
        }

        return 0 == i
    }

    ret := []string{}
    for _, val := range tmp {
        if g(val) {
            ret = append(ret, val)
        }
    }
    return ret
}

3.动态规划
  括号一定是成对出现的，可以想办法每次都添加一对括号。添加括号不能打乱已有的括号，在第n次添加的时候，可以直接在i次生成的结果外部加括号，同时拼接上j次的结果(i+j=n-1，n>1)，这样就利用了过程中的数据，效率更好。

// 代码来源
// https://leetcode-cn.com/problems/generate-parentheses/solution/dong-tai-gui-hua-yong-shi-10000-nei-cun-10000-by-c/
func generateParenthesis(n int) []string {
    if n == 0{
        return nil
    }
    if n == 1{
        return []string{"()"}
    }
    var buffer [][]string = make([][]string, n+1)
    buffer[0] = nil
    buffer[1] = []string{"()"}
    for i:=2; i<=n; i++{
        for j:=0; j<i; j++{
            buffer[i] = append(buffer[i],span2(buffer[j], buffer[i-1-j])...)
        }
    }
    return buffer[n]
}
// (as)bs
func span2(as,bs []string)[]string{
    if len(as) == 0{
        as = []string{""}
    }
    if len(bs) == 0{
        bs = []string{""}
    }
    var results []string
    for _,a := range as{
        for _,b := range bs{
            results = append(results, "("+a+")"+b)
        }
    }
    return results
}