题目描述：
给出 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
}
