leetcode 22 括号生成

递归找到所有可能解，通过判断看解是否可行，进行筛选。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        hashmap={'(':')'}
        def check(s):
            balance=0
            stack=[]
            for i in s:
                if not stack or stack[-1] not in hashmap.keys() or hashmap[stack[-1]]!=i:
                    stack.append(i)
                else:
                    if stack[-1] in hashmap.keys() and hashmap[stack[-1]]==i:
                        stack.pop()
            if  stack:
                return False
            else:return True

        def dfs(t,n,result,allresult):

            if t==n:
                if check(result):
                    allresult.append(result)
                return 


            dfs(t+1,n,result+'(',allresult)
            dfs(t+1,n,result+')',allresult)
        allresult=[]
        dfs(0,n*2,'',allresult)

        return allresult

另一种判断生成的括号序列是否合法的方法，维护一个balance值，当序列中'('就加1，否则减1，这样在循环中如果就已经balance小于0，那么就是错的，说明")" 在前面了，最后如果balance等于0，那么就是正确的。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def check(s):
            balance=0
            for i in s:

                if i=='(':
                    balance+=1
                else:
                    balance-=1
                if balance<0:
                    return False
            return balance==0

        def dfs(t,n,result,allresult):

            if t==n:
                if check(result):
                    allresult.append(result[:])
                return 


            dfs(t+1,n,result+'(',allresult)
            dfs(t+1,n,result+')',allresult)
        allresult=[]
        dfs(0,n*2,'',allresult)

        return allresult

通过维护一个left,right变量，过程中"("的数量要一直大于")"的数量，最后返回答案的时候二者数量要相等。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(left,right,n,result,allresult):
            if right>left:return 
            if left==n and left==right:

                allresult.append(''.join(result))
                return 

            if left<n:
                dfs(left+1,right,n,result+'(',allresult)

            if right<n:
                dfs(left,right+1,n,result+')',allresult)

        allresult=[]
        dfs(0,0,n,'',allresult)

        return allresult