题目

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

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

方案一（回溯/递归+set）

  1. class Solution:
  2.     def generateParenthesis(self, n: int) -> List[str]:
  3.         if n == 0:
  4.             return []
  5.         if n == 1:
  6.             return ["()"]
  8.         last = self.generateParenthesis(n - 1)
  9.         ret = set()
  10.         for each in last:
  11.             for i in range(len(each) // 2 + 1):
  12.                 ret.add(each[:i] + "()" + each[i:])
  14.         return list(ret)

方案二（回溯）

  1. class Solution:
  2.     def generateParenthesis(self, n: int) -> List[str]:
  3.         if n == 0:
  4.             return []
  5.         result = []
  6.         self.helper(n,n,'',result)
  7.         return result
  9.     def helper(self,l,r,item,result):
  10.         if r < l:
  11.             return
  12.         if l == 0 and r == 0:
  13.             result.append(item)
  14.         if l > 0:
  15.             self.helper(l-1,r,item+"(", result)
  16.         if r > 0:
  17.             self.helper(l,r-1,item+")", result)
func generateParenthesis(n int) []string {
    var res []string
    dfs("", &res, n, n)
    return res
}

// l, r 为左括号和右括号剩余的个数
func dfs(ans string, res *[]string, l, r int) {
    if l > r { // 不是有效的括号
        return
    }

    if l == 0 && r == 0 {
        *res = append(*res, ans)
        return
    }

    if l > 0 {
        dfs(ans + "(", res, l-1, r)
    }
    if r > 0 {
        dfs(ans + ")", res, l, r-1)
    }

    return
}

原文

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/287/backtracking/1285/