题目描述

[EN | CN]

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

示例:

1
2
3
4
5
6
7
8
输入:n = 3
输出:[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

解法 1:递归回溯

括号「有效」的定义是:左右不颠倒,也就是说在字符串中的任一位置,从开头到该位置的所有符号里面,左括号 ( 的数量一定要大于右括号 ) 的数量。

如此一来,我们可以从一个空串开始,逐步加上左右括号,直到长度为 2 * n,在每次添加的时候:

  • 如果长度达到 2 * n,那么得到一个有效解;
  • 如果左括号的数量小于 n,那么加上左括号,继续递归,并在结束后回溯;
  • 如果左括号的数量大于右括号的数量,那么加上右括号,继续递归,并在结束后回溯。

假设括号对数为 $n$,那么

  • 时间复杂度略;
  • 空间复杂度为 $O(n)$,递归深度。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        rets = []

        def backtrack(curr, num_left, num_right):
            if len(curr) == 2 * n:
                rets.append(curr)
                return
            if num_left < n:
                backtrack(curr + '(', num_left + 1, num_right)
            if num_left > num_right:
                backtrack(curr + ')', num_left, num_right + 1)

        backtrack('', 0, 0)
        return rets
  • 执行用时:48 ms,在所有 Python3 提交中击败了 43.67% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 6.06% 的用户。