题目

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

示例 1：输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：输入：n = 1 输出：["()"]

提示：1 <= n <= 8

注意：本题与主站 22 题相同：

解题思路分析

1、全排列-递归；时间复杂度O(4^n/n^(1/2))，空间复杂度O(4^n/n^(1/2))

var res []stringfunc generateParenthesis(n int) []string {   res = make([]string, 0)   dfs(0, 0, n, "")   return res}func dfs(left, right, max int, str string) {   if left == right && left == max {      res = append(res, str)      return   }   if left < max {      dfs(left+1, right, max, str+"(")   }   if right < left {      dfs(left, right+1, max, str+")")   }}

2、动态规划；时间复杂度O(4^n/n^(1/2))，空间复杂度O(4^n/n^(1/2))

/*dp[i]表示n=i时括号的组合dp[i]="(" + dp[j] + ")"+dp[i-j-1] (j<i)dp[0] = ""*/func generateParenthesis(n int) []string {   dp := make([][]string, n+1)   dp[0] = make([]string, 0)   if n == 0 {      return dp[0]   }   dp[0] = append(dp[0], "")   for i := 1; i <= n; i++ {      dp[i] = make([]string, 0)      for j := 0; j < i; j++ {         for _, a := range dp[j] {            for _, b := range dp[i-j-1] {               str := "(" + a + ")" + b               dp[i] = append(dp[i], str)            }         }      }   }   return dp[n]}

3、广度优先搜索；时间复杂度O(4^n/n^(1/2))，空间复杂度O(4^n/n^(1/2))

type Node struct {   str   string   left  int   right int}func generateParenthesis(n int) []string {   res := make([]string, 0)   if n == 0 {      return res   }   queue := make([]*Node, 0)   queue = append(queue, &Node{      str:   "",      left:  n,      right: n,   })   for len(queue) > 0 {      node := queue[0]      queue = queue[1:]      if node.left == 0 && node.right == 0 {         res = append(res, node.str)      }      if node.left > 0 {         queue = append(queue, &Node{            str:   node.str + "(",            left:  node.left - 1,            right: node.right,         })      }      if node.right > 0 && node.left < node.right {         queue = append(queue, &Node{            str:   node.str + ")",            left:  node.left,            right: node.right - 1,         })      }   }   return res}

Medium题目，题目同leetcode 22.括号生成、面试题08.09.括号