Stack: Generate Parenthesis Python

PHOTO EMBED

Tue Sep 27 2022 02:03:10 GMT+0000 (Coordinated Universal Time)

Saved by @bryantirawan #python #neetcode #parenthesis #open #close

def generateParenthesis(n):
    #only add parentehsis if openN < n 
    #only add close parenthesis if closeN < openN 
    #valid if open == closed == n 

    stack = []
    res = []
    
    def backtrack(openN, closeN): 
        if openN == closeN == n: 
            res.append("".join(stack))
            return 
        if openN < n: 
            stack.append('(')
            backtrack(openN + 1, closeN)
            stack.pop()
        if closeN < openN: 
            stack.append(")")
            backtrack(openN, closeN + 1)
            stack.pop()
        #stack.pop() is necessary to clean up stack and come up with other solutions 
        
    backtrack(0, 0)
    #concept is you build openN, closeN but initially, they are at 0 
    return res 

generateParenthesis(3)
content_copyCOPY

https://leetcode.com/problems/generate-parentheses/