题解 | #括号生成#

import copy
class Solution:
    # 设'('==1, ')'==-1,递归时保证arr的和>=0，就是合法的
    res = []
    def generateParenthesis(self , n: int) -> List[str]:
        num = []
        for i in range(n):
            num.append(1)
            num.append(-1)
        num.sort()
        mark = [0 for i in range(len(num))]
        arr = []
        self.full_permute(num,arr,mark)
        ans = []
        for l in Solution.res:  # 将1 -1转成( )
            s = []
            for n in l:
                s.append('(' if n==1 else ')')
            ans.append(''.join(s))
        return ans
    
    def full_permute(self,num,arr,mark):
        if len(arr) == len(num):
            Solution.res.append(copy.deepcopy(arr))
        for i in range(len(num)):
            # 判断是否已在arr中
            # 判断是否重复排列
            # 判断是否合法
            if mark[i]==1 or i>0 and num[i]==num[i-1] and mark[i-1]==0 or num[i]+sum(arr)<0:
                continue
            arr.append(num[i])
            mark[i]=1
            self.full_permute(num,arr,mark)
            arr.pop()
            mark[i]=0