Python simple stack solution without recursion


  • 1
    T
    def generateParenthesis(self, n):
        res = []
        s = [("(", 1, 0)]
        while s:
            x, l, r = s.pop()
            if l - r < 0 or l > n or r > n:
                continue
            if l == n and r == n:
                res.append(x)
            s.append((x+"(", l+1, r))
            s.append((x+")", l, r+1))
        return res
    

    variable l is current left parenthesis count

    variable r is current right parenthesis count

    l - r < 0 means this is not a valid parenthesis


Log in to reply
 

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