题目

正整数 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 []string

func 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

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.括号