22. Generate Parenthese 生成扩号

题目

给定一个 n，编写一个函数生成所有格式正确的括号

解析

1. 如何保证格式正确：
   当栈不为空的时候，我们能往栈里扔左括号和右括号，当栈为空的时候，我们只能往里扔左括号。换种说法，剩余的右括号一定要大于或者等于左括号。
2. 如何生成所有的括号组合
   把 op cp 分为两类，每次从 op 或 cp 中按顺序取出一个符号，然后排列有多少种
   即

[]str1 = fetch([]char,op-1,cp)
[]str2 = fetch([]char,op,cp-1)
rst = []str1+[]str2

所以应该是一个递归结构。每个递归结构要检查当前已有的结构是否合法。

伪代码

fetch([]char, op, cp) []string
  if op > cp
    return nil
  if op != 0
      rst1 = fetch([]char,op-1, cp)
  if cp != 0
      rst2 = fetch([]char, op,cp-1)
  return rst1+rst2

代码

func generateParenthesis(n int) []string {
    bts := make([]byte, n*2)
    return fetch(bts,0,n,n)
}

func fetch(bts []byte, idx,op,cp int) []string {
    var rst []string
    if op > cp {
        return rst
    }
    if op != 0 {
        bts[idx] = '('
        orst := fetch(bts, idx+1, op-1, cp)
        rst=append(rst, orst...)
    }
    if cp != 0 {
        bts[idx] = ')'
        crst := fetch(bts, idx+1, op, cp-1)
        rst=append(rst, crst...)
    }
    if op == 0 && cp == 0 {
        tmp := make([]byte, idx)
        for i:=0;i<idx;i++{
            tmp[i] = bts[i]
        }
        rst=append(rst, string(bts))
    }
    return rst
}

第一次提交一遍过，效率应该没问题，但是内存使用很高。我已经只复制了最后一次结果，看起来是最节约内存的做法了，难道是因为递归结构导致的？

看了一下别人的答案，因为我们返回值是 []string。这个数据在函数间传递时，rst 在每个递归里从 0 到 n 扩容，会引起底层数组多次拷贝！！！所以最好的答案是，将所有的数组扩容放在一个结果里。
同时这里要避免数组传递的误区！！！数组传递后如果扩容，可能导致原数组和当前数组指向不同的底层数组结构。这也是为什么 append 有返回值的原因！！！

func generateParenthesis(n int) []string {
    bts := make([]byte, n*2)
    rst :=make([]string,0)
    fetch(bts,0,n,n, &rst)
    return rst
}

func fetch(bts []byte, idx,op,cp int, rst *[]string) {
    if op > cp {
        return
    }
    if op != 0 {
        bts[idx] = '('
        fetch(bts, idx+1, op-1, cp, rst)
    }
    if cp != 0 {
        bts[idx] = ')'
        fetch(bts, idx+1, op, cp-1, rst)
    }
    if op == 0 && cp == 0 {
        tmp := make([]byte, idx)
        for i:=0;i<idx;i++{
            tmp[i] = bts[i]
        }
        *rst=append(*rst, string(tmp))
    }
}