题解 | #数组中的逆序对#

解题思路： 1、这道题使用递归方法求解

首先定义一个函数，这个函数目的是生成n对括号的合法组合

2、递归的第二个要素就是递归判断结束

很显然，当只有一对括号的时候，也就是n=1的时候就是["()"]

3、递归的第三要素：等价关系

我们可以观察出，当有两对括号的时候，他们的组合其实是从一对括号生成的

具体的：

（1）一对括号外部加一对括号 ==> () -> (())

（2）一对括号左边添加一对括号 ==> () -> ()()

（3）一对括号右边添加一对括号 ==> () -> ()()

（4）去掉重复的

    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        if n == 1:
            return ["()"]
        brackets = self.generateParenthesis(n-1)  # list[str]
        tempbracket = []
        for bracket in brackets:
            bracket_index = []
            # 写一个函数判断每一对函数的下标
            bracket_index = self.is_bracket_index(bracket, n-1)
            for j in range(len(bracket_index)):
                tempbracket.append(bracket[:bracket_index[j][0]]+'('+bracket[bracket_index[j][0]:bracket_index[j][1]+1] + ')' + bracket[bracket_index[j][1]+1:])  # 在中间加一个括号
                tempbracket.append(bracket[:bracket_index[j][0]]+'()'+bracket[bracket_index[j][0]:])  # 在左边加一个括号
                tempbracket.append(bracket[:bracket_index[j][1]+1]+'()'+bracket[bracket_index[j][1]+1:])  # 在右边加一个括号
        
        # 去重
        new_tempbracket = []
        for i in tempbracket:
            if i not in new_tempbracket:
                new_tempbracket.append(i)
        return new_tempbracket
    def is_bracket_index(self, bracket, n):
        bracket_index = []
        bracket_stack_1 = bracket
        bracket_stack_2 = []
        for i in range(2*n-1, -1, -1):
            if bracket[i] == ")":
                bracket_stack_2.append((i, ')'))
            else:
                bracket_index.append((i, bracket_stack_2[-1][0]))
                bracket_stack_2.pop()
        return bracket_index