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: MEDIUM
Tags: Dynamic programming

Complete search

String algorithms
Skill types: Dynamic programming

Complete search

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

Solutions:
class Solution:

	def generateParenthesis(self, n):
		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):
		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):
		if n < 1 or type(n) != int:
			return []
		ret = []
		tmp = []
		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):
		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):
		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):

		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):
		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 Solution:

	def generateParenthesis(self, n):
		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):
		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):
		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):
		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):
		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):

		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):
		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


class Solution:
	hashMap = {}
	outPut = []

	def helper(self, n, string, length, opened, openUsed):
		if length == n * 2:
			if string not in self.outPut:
				self.outPut.append(string)
			return
		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):
		self.hashMap = {}
		self.outPut = []
		self.helper(n, '', 0, 0, 0)
		return self.outPut


class Solution:

	def generateParenthesis(self, n):
		answers = []
		for i in range(0, n + 1):
			answers.append(Solution.catalanHelper(i, answers))
			print((i, answers))
		return list(set(answers[n]))

	@staticmethod
	def catalanHelper(n, answers):
		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