22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

def generateParenthesis(n: int):

        ans = []

        def backtrack(S, left, right):

            if left+right == 2*n:

                ans.append(S)

                return

            if left < n:                

                backtrack(S+"(", left+1, right)                

            if right < left:

                backtrack(S+")", left, right+1)

        backtrack("", 0, 0)

        return ans

 

def generateParenthesis(n: int):

    if n == 0: return ['']

    ans = []

    for c in range(n):

        for left in generateParenthesis(c):

            for right in generateParenthesis(n-1-c):

                ans.append('{}({})'.format(left, right))

                #ans.append('({}){}'.format(left, right)) #also correct

    return ans