题解 | #括号生成#

思想：每一个合法组合的首末位是确定的，即所有的组合都为（####)。其中，根据排列组合的知识可以知道，我们还有2n-2个位置需要确定。其中，只需要确定左括号(的位置就可以了。

代码解释：这里的基本思想是一个一个加，先从一个左括号(开始，一个循环之后变成[((,()]，然后变成[(((,((),()(,())]。但是为了括号序列的合理性，需要排除右括号比左括号多的情况，所以需要记录左括号的个数k。当左括号的个数等于所需括号的个数时，将该序列的右括号个数补齐，填入输出序列result中。

变量解释：lstmp为一个暂时变量，为了更新每次ls的值。

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        if n < 1:
            return []
        if n == 1:
            return ['()']
        a = '('
        b = ')'
        result = []
        ls = [[1,'(']]
        counter = 1
        while len(ls) > 0:
            lstmp = []
            for ele in ls:
                k = ele[0]
                strtmp = ele[1]
                if k+1 == n:
                    result.append(strtmp+a+b*(2*n-counter-1))
                else:
                    lstmp.append([k+1,strtmp+a])
                if counter-k < k:
                    ## ')'smaller than'('
                    lstmp.append([k,strtmp+b])
            counter += 1
            ls = lstmp
        return result