[LeetCode]22 括号生成

题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    d=[[""],["()"]]
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        d = self.d
        if n < len(d):
            return d[n]
        for i in range(len(d), n+1):
            t = set()
            for m in range(1, i):
                for s1 in d[i-m]:
                    for s2 in d[m]:
                        for iD in range(len(s1)+1):
                            t.add(''.join([s1[:iD], s2 , s1[iD:]]))
            d.append(list(t))
            i += 1
        return d[n]