题解 | #括号生成#
括号生成
https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca
在BM56基础上，加入剪枝操作：
- 合法的括号顺序是，'(' 和 ')' 相互抵消后，排第一的一定是'('；
- 令'('==1， ')'==-1，递归时保证，arr和>=0，就是合法的。
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
