题目：

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

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

题目的理解：

写成当n为1，2，3，4后，总结出规律为 f(3) = f(1) * f(2) + f(1)中间插入f(2)。使用递归就可以实现逻辑。

python实现

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        self.processing = dict()

        def recursion(num: int) -> set:
            if 1 == num:
                return {'()'}

            if num in self.processing.keys():
                return self.processing[num]

            temp_set = set()
            for index in range(1, num):
                left = recursion(index)
                right = recursion(num - index)

                for item1 in left:
                    for item2 in right:
                        half = len(item1) // 2
                        item3 = item1[:half] + item2 + item1[half:]

                        temp_set.add(item1 + item2)
                        temp_set.add(item3)
            self.processing[num] = temp_set

            return temp_set

        return list(recursion(n))

想看最优解法移步此处

提交

难得一次通过，看着很难的题目，当发现规律后还是很清晰的。

// END 每天过的开心，做自己喜欢做的事