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



For example, given n = 3, a solution set is:


[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Difficulty: interview

Starter code:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        

Solutions:
class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         if n == 0:
             return []
         left = right = n
         result = []
         self.generate(left, right, result, '')
         return result
     def generate(self, left, right, result, string):
         if left == 0 and right == 0:
             result.append(string)
             return
         if left:
             self.generate(left - 1, right , result, string+'(')
         if left < right:
             self.generate(left, right - 1, result, string+')')


class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         self.mem = {}
         
         return self.top_down(n)
         
         
     def merge(self, left, right):
         comb = []
         for i in left:
             comb += [i + j for j in right]
         
         return list(set(comb))
         
     def top_down(self, n):
         if n == 1:
             return ['()']
         
         if not n-1 in self.mem:
             self.mem[n-1] = self.top_down(n-1)
         rest = self.mem[n-1]
         comb = ['(' + i + ')' for i in rest]
         
         for i in range(1, n):
             
             if not i in self.mem:
                 self.mem[i] = self.top_down(i)
             comb_left = self.mem[i]
             if not n-i in self.mem:
                 self.mem[n-i] = self.top_down(n-i)
             comb_right = self.mem[n-i]
             
             comb += self.merge(comb_left,comb_right)
             
         
         comb = list(set(comb))
         
         return comb
     


class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         if n < 1 or type(n) != int:
             return []
         ret = []
         tmp = []
         # define a set of struct like {str:"((())", cnt:3, rcnt:2)}
         tmp.append({"str": "(", "cnt": 1, "rcnt": 0})
         while tmp:
             cur = tmp.pop()
             if n == cur["cnt"]:
                 ret.append(cur["str"] + ')'*(n - cur["rcnt"]))
             else:
                 if cur["cnt"] > cur["rcnt"]:
                     tmp.append({"str":cur["str"]+')', "cnt": cur["cnt"], "rcnt": cur["rcnt"] + 1})
                 tmp.append({"str":cur["str"]+'(', "cnt": cur["cnt"] + 1, "rcnt": cur["rcnt"]})
         return ret


class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         stack = []
         s = ''
         self.dfs(stack, 0, 0, s, n)
         return stack
 
     def dfs(self, stack, first, last, s, n):
         if last==n:
             stack.append(s)
         else:
             if first < n:
                 self.dfs(stack, first+1, last, s+'(', n)
             if last < first:
                 self.dfs(stack, first, last+1, s+')', n)     

class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         ret = []
         def backtrack(left = 0, right = 0, tmp = ''):
             if len(tmp) == 2 * n:
                 ret.append(tmp)
                 return
             if left < n:
                 backtrack(left + 1, right, tmp + '(')
             if left > right:
                 backtrack(left, right + 1, tmp + ')')
         
         backtrack()
         return ret

class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         # if n==0:
         #     return [""]
         # prev = self.generateParenthesis(n-1)
         # results = set()
         # for r in prev:
         #     results.add('('+r+')')
         #     results.add('()'+r)
         #     results.add(r+'()')
         # return sorted(list(set(results)))
         
         def gen(n,open_par,res,res_set):
             print(res)
             if len(res)==2*n:
                 res_set.append(''.join(res))
                 return
             if 2*n-len(res)>open_par:
                 res.append('(')
                 gen(n,open_par+1,res,res_set)
                 res.pop()
             if open_par>0:
                 res.append(')')
                 gen(n,open_par-1,res,res_set)
                 res.pop()
         res_set=[]
         gen(n,0,[],res_set)
         return res_set


class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         result = set()
         if n == 0:
             result = [""]
         else:
             for i in range(1, n + 1):
                 temp1 = {
                     "(" + x + ")" for x in self.generateParenthesis(i - 1)}
                 temp2 = {x for x in self.generateParenthesis(n - i)}
                 temp = {x + y for x in temp1 for y in temp2} | {x +
                                                                 y for x in temp2 for y in temp1}
                 result = result | temp
 
             result = sorted(list(result))
         return result


class Node(object):
     def __init__(self,val,root,n,p):
         self.val=val
         self.n=n
         self.p=p
         if root:
             self.root=root
         else:
             self.root=self
         self.left=self.leftchild(n,p)
         self.right=self.rightchild(n,p)
            
     def leftchild(self,n,p):
         if n==0:
             if p==0:                 
                 temp=''.join(self.val);
                 self.root.val.append(temp)
             return None
 
         if n>0:
             return Node(self.val+['('],self.root,n-1,p+1)
 
     def rightchild(self,n,p):
         if p==0:
               return None
         else:
               return Node(self.val+[')'],self.root,n,p-1)
             
 
 class Solution:
     def generateParenthesis(self, s):
         """
         :type nums: List[int]
         :rtype: void Do not return anything, modify nums in-place instead.
         """
         D=Node([],None,s,0)
         return D.val
 
         
                

class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         rst = []
         cake = ''
         self.generateRecursion(rst,cake,n,n)
         return rst
     def generateRecursion(self,rst,cake,left,right):
         if right==0:
             rst.append(cake)
         if left>0:
             self.generateRecursion(rst,cake+'(',left-1,right)
         if right>left:
             self.generateRecursion(rst,cake+')',left,right-1)


class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         if not n:
             return []
         cache = [["(", 1, n-1]]
         for _ in range(2*n-1):
             for _ in range(len(cache)):
                 temp = cache.pop(0)
                 if temp[1]:
                     toAdd = temp.copy()
                     toAdd[0] += ')'
                     toAdd[1] -= 1
                     cache.append(toAdd)
                 if temp[2]:
                     temp[0] += '('
                     temp[1] += 1
                     temp[2] -= 1
                     cache.append(temp)
         return [items[0] for items in cache]


class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         self.res = []
         self.dfs(n, 0, 0, '')
         return self.res
 
     def dfs(self, n, left, right, path):
         if left > n or right > n:
             return
 
         if n == 0:
             self.res.append(path)
             return
 
         if left == 0:
             self.dfs(n, left+1, right, path+'(')
 
         if left == right and left != 0:
             self.dfs(n-left, 0, 0, path)
 
         if left > right:
             self.dfs(n, left+1, right, path+'(')
             self.dfs(n, left, right+1, path+')')

class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         if n == 0:
             return [""]
         if n == 1:
             return ["()"]
         results = []
 
         for i in range(1, 2*n, 2):
             first = self.generateParenthesis(int((i-1)/2))
             second = self.generateParenthesis(int((2*n-i-1)/2))
             results += ["("+u+")"+v for u in first for v in second]
         return  results

class Solution:
     def parenthesis(self, n):
         return "("*n+")"*n
     
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         if n == 0:
             return []
         elif n == 1:
             return ["()"]
         
         result = []
         for i in range(1,n):
             r1 = self.generateParenthesis(i)
             r2 = self.generateParenthesis(n-i)
             for r11 in r1:
                 for r21 in r2:
                     result.append(r11+r21)
                     
         r3 = self.generateParenthesis(n-1)
         for r31 in r3:
             result.append("({})".format(r31))
         
         result.sort()
         rr = []
         last = None
         for r in result:
             if r == last:
                 continue
             rr.append(r)
             last = r
             
                 
         return rr


class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         
         def balance(str):
             lst = list(str)
             bal = 0
             for char in lst:
                 if char == "(":
                     bal += 1
                 else:
                     bal -= 1
             return bal
         
         def left(str):
             lst = list(str)
             sum = 0
             for char in lst:
                 if char == "(":
                     sum += 1
             return n - sum
         
         def right(str):
             lst = list(str)
             sum = 0
             for char in lst:
                 if char == ")":
                     sum += 1
             return n - sum
         
 
         prev = ["("]
         length = 1
         
         while length < 2*n:
             current = [] 
                 
             for item in prev:
                 if left(item) != 0:
                     current.append(item+"(")
                     
                 if right(item) != 0 and balance(item) > 0:
                     current.append(item+")")
             length += 1
             prev = current
         
         return prev

class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         results = []
         
         def genparen(prefix, opens, closes):
             if len(prefix) == 2*n:
                 results.append(prefix)
                 return
             
             if opens < n:
                 genparen(prefix+"(", opens+1, closes)
             if closes < opens:
                 genparen(prefix+")", opens, closes+1)
         
         genparen('', 0, 0)
         return results
             
         
         
 #         paren_map = {}
 #         paren_map[1] = set(["()"])
         
 #         for i in range(2, n+1):
 #             paren_map[i] = self.generate_parens(paren_map[i-1])
             
 #         return list(paren_map[n])
             
             
 #     def generate_parens(self, st):
 #         result = set()
         
 #         for elem in st:
 #             for i in range(len(elem)):
 #                 candidate = elem[:i] + "()" + elem[i:]
 #                 result.add(candidate)
         
 #         return result
         


class Solution:
     
     hashMap = {}
     outPut = []
     
     def helper(self, n, string, length, opened, openUsed):
         
         ## base case
         if length == n*2:
             if string not in self.outPut:
                 self.outPut.append(string)
             return
         
         ## skip if already tried
         if string in self.hashMap:
             return
         else:
             self.hashMap[string] = 1
         
         if opened == 0:
             tempOpened = 1
             tempOpenUsed = openUsed + 1
             self.helper(n,string+'(',length+1,tempOpened,tempOpenUsed)
             
         if opened > 0:
             tempOpened = opened - 1
             self.helper(n,string+')',length+1,tempOpened,openUsed)
             
         if openUsed < n:
             tempOpened = opened + 1
             tempOpenUsed = openUsed + 1
             self.helper(n,string+'(',length+1,tempOpened,tempOpenUsed)
     
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         self.hashMap = {}
         self.outPut = []
         self.helper(n,"",0,0,0)
         
         return self.outPut
         
         


class Solution:
     def generateParenthesis(self, n):
         """
         :type n: int
         :rtype: List[str]
         """
         # array to keep track of results         
         answers = []
         for i in range(0,n+1):
             answers.append(Solution.catalanHelper(i, answers))
             print((i, answers))
         
         return list(set(answers[n]))
         
     @staticmethod
     # returns parenthesis
     def catalanHelper(n, answers):
         """
         : type n : int 
         : rtype : List[str]
         """
         
         if n == 0:
             return [""]
         elif n == 1:
             return ["()"]
         else:
             output = []
             for i in range(0, n-1):
                 front_list = answers[i] 
                 end_list = answers[n-i-1]
                 for front in front_list:
                     for end in end_list:
                         
                         output.append("(" + front + ")" + end )
                         output.append("(" + front  + end +")")
 
             return output