22. 括号生成

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

示例 1：

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

示例 2：

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

DFS

维护一个 leftNum 来表示之前剩余的、没有被匹配到的左括号个数

func generateParenthesis(n int) []string {
	count := n * 2
	res := make([]string, 0)
	var dfs func(quotes []byte, layer, leftNum int) // leftNum 表示之前剩余多少个没有被匹配到的左括号
	dfs = func(quotes []byte, layer, leftNum int) {
		if layer == count {
			if leftNum == 0 {
				res = append(res, string(quotes))
			}
			return
		}

		if leftNum >= 1 {
			dfs(append(quotes, ')'), layer+1, leftNum-1)
		}
		dfs(append(quotes, '('), layer+1, leftNum+1)
	}
	dfs([]byte{}, 0, 0)
	return res
}

⭐ 更加标准的 DFS 回溯

回溯法还原变量

func generateParenthesis(n int) []string {
	count := n * 2
	res := make([]string, 0)
	var dfs func(quotes []byte, layer, leftNum int) // leftNum 表示之前剩余多少个没有被匹配到的左括号
	dfs = func(quotes []byte, layer, leftNum int) {
		if layer == count {
			if leftNum == 0 {
                // 这里不用 copy, 因为 string 函数直接深拷贝了
				res = append(res, string(quotes))
			}
			return
		}

		if leftNum >= 1 {
			quotes = append(quotes, ')')
			dfs(quotes, layer+1, leftNum-1)
			quotes = quotes[:len(quotes)-1]
		}
		quotes = append(quotes, '(')
		dfs(quotes, layer+1, leftNum+1)
		quotes = quotes[:len(quotes)-1]
	}
	dfs([]byte{}, 0, 0)
	return res
}

DP

题解：https://leetcode-cn.com/problems/generate-parentheses/solution/zui-jian-dan-yi-dong-de-dong-tai-gui-hua-bu-lun-da/

好屌！

func generateParenthesis(n int) []string {
   if n == 1 {
      return []string{"()"}
   }
   dp := [][]string{{""}, {"()"}}

   for i := 2; i <= n; i++ {
      dpi := make([]string, 0) // dp[i]
      for p := 0; p <= i-1; p++ {
         q := i - 1 - p
         // 遍历dp[p]和dp[q]中的所有组合
         for _, quotes1 := range dp[p] {
            for _, quotes2 := range dp[q] {
               dpi = append(dpi, "("+quotes1+")"+quotes2)
            }
         }
      }
      dp = append(dp, dpi)
   }
   return dp[n]
}