0023 - Generate Parentheses

You are given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.

Example 1:

Input: n = 1

Output: ["()"] Example 2:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"] You may return the answer in any order.

Solution¶

• only add open paranthesis if open<n
• only add a close paranthesis if closed<open
• valid if open == closed ==n https://www.youtube.com/watch?v=s9fokUqJ76A https://www.youtube.com/watch?v=oC4saZRNwfI

In [1]:

def generateParenthesis(n):
    stack, res=[], []
    def backtrack(open, close):
        if open == close == n:
            res.append("".join(stack))
            return
        if open<n:
            stack.append("(")
            backtrack(open+1,close)
            stack.pop()
        if close<open:
            stack.append(")")
            backtrack(open,close+1)
            stack.pop()
    backtrack(0,0)
    return stack

In [ ]: