[22][中等][回溯][BFS] 括号生成

题目描述

22. 括号生成

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

示例：

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

解题思路

回溯

回溯算法的基本思想是: 从一条路往前走, 能进则进, 不能进则退回来, 换一条路再试.

这道题即递归地增加括号, 每次增加有两种选择, 左括号和右括号. 当然每种需要满足一定的条件才能增加, 否则这条路是堵死的:

• 左括号: 左括号的数量小于$n$时都可以增加

• 右括号: 首先要求右括号的数量同样要小于$n$, 而且同是要已有的右括号的数量要小于左括号的数量, 两者同时满足时才能增加

回溯需要一个停止条件, 本题的停止条件很明显, 当前生成的字符串长度等于$n*2$就需要停止了, 停止后, 将这个字符串加入到最后的结果列表中.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def gen(current, unused, used, result):
            if unused == 0 and used == n:
                result.append(current)

            if unused > 0:
                gen(current + '(', unused - 1, used, result)
            if used + unused < n and used < n:
                gen(current + ')', unused, used + 1, result)
            return result
        res = []
        gen('', n, 0, res)
        return res