📑 题目：22. 括号生成

🚀 本题 LeetCode 传送门

题目大意

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

解题思路

  • 这道题乍一看需要判断括号是否匹配的问题，如果真的判断了，那时间复杂度就到 O(n * 2^n)了，虽然也可以 AC，但是时间复杂度巨高。
  • 这道题实际上不需要判断括号是否匹配的问题。因为在 DFS 回溯的过程中，会让 ( 和 ) 成对的匹配上的。

代码

  1. package leetcode
  3. func generateParenthesis(n int) []string {
  4.  if n == 0 {
  5.   return []string{}
  6.  }
  7.  res := []string{}
  8.  findGenerateParenthesis(n, n, "", &res)
  9.  return res
  10. }
  12. func findGenerateParenthesis(lindex, rindex int, str string, res *[]string) {
  13.  if lindex == 0 && rindex == 0 {
  14.   *res = append(*res, str)
  15.   return
  16.  }
  17.  if lindex > 0 {
  18.   findGenerateParenthesis(lindex-1, rindex, str+"(", res)
  19.  }
  20.  if rindex > 0 && lindex < rindex {
  21.   findGenerateParenthesis(lindex, rindex-1, str+")", res)
  22.  }
  23. }