❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/generate-parentheses/

❞

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 「有效的」 括号组合。

示例 1：

var (
    ans []string
    size int
    )
func generateParenthesis(n int) []string {
    ans = []string{}
    size = n
    // 以左括号开始
    path := "("

    dfs(path, 1, 1, 0)

    return ans
}

func dfs(path string, index int, left int, right int){
    if left > size {
        return
    }
    if right > size {
        return
    }
    if(right > left){
        return
    }

    if index == (2 * size) {
        ans = append(ans, path)
    }

  
    dfs(path + "(", index + 1, left + 1, right)
    
    dfs(path + ")", index + 1, left, right + 1)

}

剪枝后优化效果非常明显。

复杂度分析

• 时间复杂度： 。总的节点个数为 个，除掉右半边，可以按照 个计算。
• 空间复杂度： ，ch 数组长度为 2n，递归深度也是 2n。