LeetCode 解题报告 (22)-- 生成所有合法的嵌套括号

发表于 标签 ，

原题如下：
>Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

>For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

题目要求生成给定数量的所有合法嵌套括号，最直观的想法是通过穷举得到所有的组合结果，再判断每个是否合法，但是这样的时间复杂度太大，会导致 TLE。

既然上面的方法会导致 TLE, 那么能不能在构造的过程中判断目前所构造的嵌套括号是否合法？

答案是可以的，只需要遵循以下的两条规则即可:
1. 只要 "(" 的数量没有超过 n，都可以插入 "("。
2. 而可以插入 ")" 的前提则是当前的 "(" 数量必须要多余当前的 ")" 数量。

通过回溯法能够实现这个判断并构造出所有合法的嵌套括号，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):  
    def generateParenthesis(self, n):  
        """  
        :type n: int  
        :rtype: List[str]  
        """  
        res = []  
        self.helper(n,n,'',res)  
        return res

    def  helper(self,left,right,item,res):  
        if left==0 and right==0:  
            res.append(item)  
            return  
        if left>0:  
            self.helper(left-1,right,item+'(',res)  
        if right>left:  
            self.helper(left,right-1,item+')',res)