Recursive solution in Python (using stack)

  • 0
    class Solution(object):
        def generateParenthesis(self, n):
            :type n: int
            :rtype: List[str]
            res = []
            def gen_paren(n, stack, item):
                if n == 0:  # all left halves have been added, pop the right halves in stack
                    while len(stack) != 0:
                        item = item + stack.pop()
                    res.append(item)    # append this string to list
                stack = stack[:] # create new list and copy their items
                if len(stack) == 0: # stack is null, so only left half can be added
                    gen_paren(n-1, stack+[')'], item+'(')
                else:   # stack is not null, there are two options
                    # add left half
                    gen_paren(n-1, stack+[')'], item+'(')
                    # add right half and pop the stack
                    gen_paren(n, stack, item+')')
            if n == 0:
                return []
            gen_paren(n, [], '')
            return res

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.