22. Generate Parentheses

[mengyushi]

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        '''
        left: # of '('
        right: # of ')'

        if left >= right: 
            1). add more ')'
            2). add more '(' (if not finished)

        if right > left: ())))) wrong. do not go further

        '''

        ans = []

        def backtrack(S="", left = 0, right = 0):
            if len(S) == 2 * n:
                ans.append(S)
                return 

            if left < n:
                backtrack(S+'(', left+1, right)

            if right < left:
                backtrack(S+')', left, right+1)

        backtrack()
        return ans