22.括号生成

leetcode

先选定一对括号，生成的序列可以写为(left)right，其中 left 和 right 分别为 i 对括号和 n-i-1 对括号的序列。

再利用递归计算 left 和 right 。

时间复杂度：O(4n/√n)
空间复杂度：O(4n/√n)

var cache = make(map[int][]string)

func generateParenthesis(n int) []string {
    return generate(n)
}

func generate(n int) []string {
    if n == 0 {
        return []string{""}
    }

    if n == 1 {
        return []string{"()"}
    }

    if c, ok := cache[n]; ok {
        return c
    }

    result := []string{}
    for i := 0; i < n; i++ {
        left := generate(i)
        right := generate(n - i -1)
        
        for _, l := range left {
            temp := fmt.Sprintf("(%s)", l)
            for _, r := range right {
                result = append(result, fmt.Sprintf("%s%s", temp, r))
            }
        }

    }

    cache[n] = result
    return result
}