Generate Parantheses

Bruteforce builder

Problem

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

For example:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Input: n = 1
Output: ["()"]

Thought Process

• We aren't given a "normal" input to recurse on like we usually get with backtracking problems but we are actually recursing on bracket placements.

• We will add the closing bracket if there is at least one open bracket placed down. For n open brackets there must be n closing brackets to complement, and the final valid placement will be of length n*2.

• ( (( ((( ((() ((()) ((())) i (() (()( (()() (()()) (()) (())( (())() () ()( ()(( ()(() ()(()) ()() ()()( ()()()

Solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        soln = []
        self.helper(soln, "", n,n,n)
        return soln
    
    def helper(self, soln, s, left, right, n):
        if len(s) == (n*2):
            soln.append(s)
        if left > 0:
            self.helper(soln, s+"(", left-1,right,n)
        if right > left:
            self.helper(soln, s+")", left, right-1, n)
        

Key Points

• In this problem, you have to choose between left and right parenthesis.

• The idea here is to only add '(' and ')' that we know will guarantee us a solution (instead of adding 1 too many close). Once we add a '(' we will then discard it and try a ')' which can only close a valid '('. Each of these steps are recursively called.

• Every time you choose a "(" means making another ")" available.

Time Complexity

Time: $O(2^{2n})$because we need to make a choice of either left or right (that makes it $2^n$ ) and then we need n left parthesis and n right parenthesis ($2n$).

Space: $O(n)$ as this will be the max depth of the recursion stack (look at Thought Process picture)