leetcodeday –22括号生成

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

思路：递归，对于每对（）=>下一次会变成 （）（） or （（））

因此找到所有的括号对的首尾位置，然后进行替换就ok

# [22] 括号生成
#

# @lc code=start
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def gpt(n):
            if n == 1:
                return ["()"]
            List=gpt(n-1)
            lens=len(List)
            l1,rev=list(),list()
            for i in range(lens):
                s1=List[i]
                 #Z=[]
                l1.append((0,s1[0]))
                for i in range(1,len(s1)):
                    if s1[i]==")":
             
                        y=l1.pop()[0]
                        #Z.append((y,x))
                        rev.append(s1[0:i+1]+"()"+s1[i+1:])
                        rev.append(s1[0:y+1]+"()"+s1[y+1:])
            

                    else: l1.append((i,s1[i]))
            return list(set(rev))
        return gpt(n)