Given an integer N representing the number of pairs of parentheses, the task is to generate all combinations of well-formed(balanced) parentheses.
Example 1:
Input:
N = 3
Output:
((()))
(()())
(())()
()(())
()()()
Example 2:
Input:
N = 1
Output:
()
Your Task:  
You don't need to read input or print anything. Complete the function AllParenthesis() which takes N as input parameter and returns the list of balanced parenthesis.
Expected Time Complexity: O(2^{N} * N).
Expected Auxiliary Space: O(2*N*X), X = Number of valid Parenthesis.
Constraints: 
1 ≤ N ≤ 12

Difficulty: MEDIUM
Tags: Complete search
Skill types: Complete search
Expected Time Complexity: O(2^{N} * N).
Expected Auxiliary Space: O(2*N*X), X = Number of valid Parenthesis.

Starter code:
#User function Template for python3

class Solution:
    def AllParenthesis(self,n):
        #code here


Solutions:
class Solution:

	def util(self, o, c, s, ans):
		if o < 0 or c < 0:
			return
		if o == 0 and c == 0:
			ans.append(s)
			return
		if o == c:
			self.util(o - 1, c, s + '(', ans)
		else:
			self.util(o - 1, c, s + '(', ans)
			self.util(o, c - 1, s + ')', ans)

	def AllParenthesis(self, n):
		ans = []
		self.util(n, n, '', ans)
		return ans


class Solution:

	def AllParenthesis(self, n):
		ans = [[]]

		def make(s, opn, clos, n):
			if len(s) == 2 * n:
				ans[0].append(s)
				return
			if opn < n:
				make(s + '(', opn + 1, clos, n)
			if clos < opn:
				make(s + ')', opn, clos + 1, n)
			return
		make('', 0, 0, n)
		return ans[0]


class Solution:

	def para(self, arr, str, o, n):
		if len(str) == 2 * n:
			arr.append(str)
			return
		if n - o > 0:
			self.para(arr, str + '(', o + 1, n)
		if o > len(str) - o:
			self.para(arr, str + ')', o, n)
		return

	def AllParenthesis(self, n):
		arr = []
		if n > 0:
			self.para(arr, '(', 1, n)
			return arr
		else:
			return ''


class Solution:

	def solve(self, open, close, opt='', ret=[]):
		if open == 0 and close == 0:
			ret.append(opt)
			return ret
		if open > 0:
			self.solve(open - 1, close, opt + '(', ret)
		if close > open and close > 0:
			self.solve(open, close - 1, opt + ')', ret)
		return ret

	def AllParenthesis(self, n):
		return self.solve(open=n, close=n, opt='', ret=[])


class Solution:

	def AllParenthesis(self, n):

		def solve(Open, close, ans, s):
			if Open == 0 and close == 0:
				ans.append(s)
			if Open > 0:
				solve(Open - 1, close, ans, s + '(')
			if close > 0 and close > Open:
				solve(Open, close - 1, ans, s + ')')
		ans = []
		solve(n, n, ans, '')
		return ans


class Solution:

	def AllParenthesis(self, n):
		arr = []
		kmap = set()

		def solve(lc, rc, ans):
			if lc < 0 or rc < 0:
				return
			if lc == 0 and rc == 0:
				kmap.add(ans)
				return
			if lc > 0:
				solve(lc - 1, rc, ans + '(')
			if rc > lc:
				solve(lc, rc - 1, ans + ')')
			return
		solve(n, n, '')
		return list(kmap)


class Solution:

	def genparan(self, n, stringsofar, paranopen, paranclose):
		if len(stringsofar) == 2 * n:
			self.res.append(stringsofar)
			return
		if paranopen < n:
			self.genparan(n, stringsofar + '(', paranopen + 1, paranclose)
		if paranclose < paranopen:
			self.genparan(n, stringsofar + ')', paranopen, paranclose + 1)

	def AllParenthesis(self, n):
		self.res = []
		self.genparan(n, '', 0, 0)
		return self.res


class Solution:

	def boobs(self, n, str, o, c, res):
		if o == n and c == n:
			res.append(str)
			return
		if o < n:
			self.boobs(n, str + '(', o + 1, c, res)
		if c < o:
			self.boobs(n, str + ')', o, c + 1, res)

	def AllParenthesis(self, n):
		res = []
		str = ''
		o = 0
		c = 0
		self.boobs(n, str, o, c, res)
		return res


class Solution:

	def getBrackets(self, c, o, str, arr):
		if c < o or c < 0 or o < 0:
			return
		if c == 0 and o == 0:
			arr.append(str)
		else:
			self.getBrackets(c - 1, o, str + ')', arr)
			self.getBrackets(c, o - 1, str + '(', arr)

	def AllParenthesis(self, n):
		arr = []
		self.getBrackets(n, n, '', arr)
		return arr


class Solution:

	def AllParenthesis(self, n):

		def solve(open, close, op, res):
			if open == 0 and close == 0:
				res.append(op)
				return res
			if open != 0:
				op1 = op
				op1 = op1 + '('
				solve(open - 1, close, op1, res)
			if close > open:
				op2 = op
				op2 = op2 + ')'
				solve(open, close - 1, op2, res)
			return
		res = []
		close = n
		open = n
		op = ''
		solve(open, close, op, res)
		return res


class Solution:

	def AllParenthesis(self, n):
		res = []
		self.dfs(n, 0, 0, '', res)
		return res

	def dfs(self, n, op, cl, s, res):
		if len(s) == n * 2:
			res.append(s)
			return
		if op < n:
			self.dfs(n, op + 1, cl, s + '(', res)
		if cl < op:
			self.dfs(n, op, cl + 1, s + ')', res)


class Solution:

	def AllParenthesis(self, n):
		res = []
		st = []

		def back(s, e):
			if s == e == n:
				res.append(''.join(st))
				return
			if s < n:
				st.append('(')
				back(s + 1, e)
				st.pop()
			if e < s:
				st.append(')')
				back(s, e + 1)
				st.pop()
		back(0, 0)
		return res


class Solution:

	def AllParenthesis(self, n):

		def generate(l, r, t):
			if l > n or r > n or l < r:
				return
			if l == n and r == n:
				ans.append(t)
				return
			generate(l + 1, r, t + '(')
			generate(l, r + 1, t + ')')
		ans = []
		generate(0, 0, '')
		return ans


class Solution:

	def AllParenthesis(self, n):
		res = []

		def recur(st, op, cl):
			if op == cl == n:
				res.append(st[:])
				return
			if op < n:
				recur(st + '(', op + 1, cl)
			if cl < op:
				recur(st + ')', op, cl + 1)
		recur('', 0, 0)
		return res


class Solution:

	def brack(self, n, ans, pos, cou, b):
		if n * 2 == pos:
			self.res.append(ans)
			return
		if cou != n:
			self.brack(n, ans + '(', pos + 1, cou + 1, b - 1)
		if len(ans) > 0 and b < 0:
			self.brack(n, ans + ')', pos + 1, cou, b + 1)

	def AllParenthesis(self, n):
		self.res = []
		self.brack(n, '', 0, 0, 0)
		return self.res


class Solution:

	def AllParenthesis(self, n):

		def generate(openn, close, out, res):
			if openn == 0 and close == 0:
				res.append(out)
				return
			if openn > 0:
				out1 = out
				out1 = out1 + '('
				generate(openn - 1, close, out1, res)
			if close > openn:
				out2 = out
				out2 = out2 + ')'
				generate(openn, close - 1, out2, res)
			return
		openn = n
		close = n
		out = ''
		res = []
		generate(openn, close, out, res)
		return res


class Solution:

	def AllParenthesis(self, n):

		def helper(o, c, cur, n, res):
			if o == n and c == n:
				res.append(cur)
				return
			if o < n:
				helper(o + 1, c, cur + '(', n, res)
			if c < o:
				helper(o, c + 1, cur + ')', n, res)
		res = []
		helper(0, 0, '', n, res)
		return res


class Solution:

	def AllParenthesis(self, n):

		def Parenthesis(a, n, o, c):
			if o == n and c == n:
				l.append(''.join(a))
				return
			ac = a.copy()
			if o < n:
				a.append('(')
				Parenthesis(a, n, o + 1, c)
			if c < o:
				ac.append(')')
				Parenthesis(ac, n, o, c + 1)
		l = []
		Parenthesis(['('], n, 1, 0)
		return l


class Solution:

	def AllParenthesis(self, n):
		ans = []

		def backtrack(open, close, n, curr_str):
			if len(curr_str) == n * 2:
				ans.append(curr_str)
			if open < n:
				backtrack(open + 1, close, n, curr_str + '(')
			if close < open:
				backtrack(open, close + 1, n, curr_str + ')')
			return ans
		return backtrack(0, 0, n, '')


class Solution:

	def AllParenthesis(self, n):

		def helper(opn, close, op, ans):
			if opn == 0 and close == 0:
				ans.append(op)
				return
			if opn != 0:
				op1 = op
				op1 += '('
				helper(opn - 1, close, op1, ans)
			if opn < close:
				op2 = op
				op2 += ')'
				helper(opn, close - 1, op2, ans)
			return
		ans = []
		opn = n
		close = n
		op = ''
		helper(opn, close, op, ans)
		return ans


class Solution:

	def AllParenthesis(self, n):
		ans = []
		stack = []

		def helper(openp, closep):
			if openp == closep == n:
				ans.append(''.join(stack))
				return
			if openp < n:
				stack.append('(')
				helper(openp + 1, closep)
				stack.pop()
			if openp > closep:
				stack.append(')')
				helper(openp, closep + 1)
				stack.pop()
		helper(0, 0)
		return ans


class Solution:

	def AllParenthesis(self, n):
		res = []
		stack = []

		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 openN > closeN:
				stack.append(')')
				backtrack(openN, closeN + 1)
				stack.pop()
		backtrack(0, 0)
		return res


class Solution:

	def AllParenthesis(self, n):
		self.arr = []
		cl = op = 0
		self.recur(n, cl, op, '')
		return self.arr

	def recur(self, n, cl, op, s):
		if cl == n:
			self.arr.append(s)
			return
		if op > cl:
			if op != n:
				self.recur(n, cl, op + 1, s + '(')
			self.recur(n, cl + 1, op, s + ')')
		if op == cl:
			self.recur(n, cl, op + 1, s + '(')


class Solution:

	def AllParenthesis(str, n):
		result = []

		def backtrack(curr, left, right):
			if left == right == n:
				result.append(curr)
				return
			if left < n:
				backtrack(curr + '(', left + 1, right)
			if right < left:
				backtrack(curr + ')', left, right + 1)
		backtrack('', 0, 0)
		return result


class Solution:

	def solve(self, n, s, ans, left, right):
		if left < right:
			return
		if left == n and right == n:
			ans.append(s)
			return
		if left != n:
			self.solve(n, s + '(', ans, left + 1, right)
		if right != n:
			self.solve(n, s + ')', ans, left, right + 1)

	def AllParenthesis(self, n):
		count = 0
		s = ''
		ans = []
		self.solve(n, s, ans, 0, 0)
		return ans


class Solution:

	def AllParenthesis(self, n):
		res = []

		def helper(total, count_open, count_close, s):
			if total == 2 * n:
				return res.append(s)
			if count_open < n:
				helper(total + 1, count_open + 1, count_close, s + '(')
			if count_close < count_open:
				helper(total + 1, count_open, count_close + 1, s + ')')
		helper(0, 0, 0, '')
		return res


class Solution:

	def AllParenthesis(self, n):
		li = []

		def solve(li, tempstr, open, close):
			if len(tempstr) == 2 * n:
				li.append(tempstr)
				return
			if open < n:
				tempstr += '('
				solve(li, tempstr, open + 1, close)
				tempstr = tempstr[:-1]
			if close < open:
				tempstr += ')'
				solve(li, tempstr, open, close + 1)
				tempstr = tempstr[:-1]
		solve(li, '', 0, 0)
		return li


class Solution:

	def AllParenthesis(self, n):
		ans = []

		def helper(left, right, string):
			nonlocal ans, n
			if left == n and right == n:
				ans.append(string)
			elif right > left:
				return
			else:
				if left > right:
					helper(left, right + 1, string + ')')
				if left < n:
					helper(left + 1, right, string + '(')
		helper(0, 0, '')
		return ans


class Solution:

	def AllParenthesis(self, n):
		ans = []

		def generate(left, right, n, s):
			if left > n or right > left:
				return
			if left == n and right == n:
				ans.append(s)
				return
			generate(left + 1, right, n, s + '(')
			generate(left, right + 1, n, s + ')')
		generate(0, 0, n, '')
		return ans


class Solution:

	def AllParenthesis(self, n):
		lp = n
		rp = n
		s1 = []
		val = ''

		def param(lp, rp, val, s1):
			if lp == 0 and rp == 0:
				s1.append(val)
				return
			if lp > 0:
				val1 = val
				val1 = val1 + '('
				param(lp - 1, rp, val1, s1)
			if rp > lp:
				val2 = val
				val2 = val2 + ')'
				param(lp, rp - 1, val2, s1)
		param(lp, rp, val, s1)
		return s1


class Solution:

	def AllParenthesis(self, n):
		ans = []

		def func(op, end, s):
			if op == 0 and end == 0:
				ans.append(s)
				return
			if op < 0 or end < 0:
				return
			elif op < end:
				func(op, end - 1, s + ')')
				func(op - 1, end, s + '(')
			elif op == end:
				func(op - 1, end, s + '(')
			return
		func(n, n, '')
		return ans


class Solution:

	def AllParenthesis(self, n):

		def paren(n, res, curr, op, cl):
			if op == n and cl == n:
				res.append(curr)
				return
			if op > n:
				return
			paren(n, res, curr + '(', op + 1, cl)
			if op > cl:
				paren(n, res, curr + ')', op, cl + 1)
		res = []
		paren(n, res, '', 0, 0)
		return res


class Solution:

	def AllParenthesis(self, n):

		def paren(n, res, curr, op, cl):
			if len(curr) == 2 * n:
				if op == cl:
					res.append(curr)
				return
			if op < n:
				temp = curr
				curr += '('
				op += 1
				paren(n, res, curr, op, cl)
				curr = temp
				del temp
				op -= 1
			if op > cl:
				temp = curr
				curr += ')'
				cl += 1
				paren(n, res, curr, op, cl)
		res = []
		paren(n, res, '', 0, 0)
		return res


class Solution:

	def AllParenthesis(self, n):

		def solve(open, close, st, res):
			if open == close == 0:
				res.append(st)
				return
			if open > 0:
				st1 = st
				st1 += '('
				solve(open - 1, close, st1, res)
			if close > open:
				st2 = st
				st2 += ')'
				solve(open, close - 1, st2, res)
			return
		string = '('
		array = []
		solve(n - 1, n, string, array)
		return array


class Solution:

	def AllParenthesis(self, n):

		def checkAllComb(str, oB, cB, n, ans):
			if oB == n and cB == n:
				ans.append(str)
				return
			if oB > cB:
				checkAllComb(str + ')', oB, cB + 1, n, ans)
			if oB < n:
				checkAllComb(str + '(', oB + 1, cB, n, ans)
		ans = []
		checkAllComb('', 0, 0, n, ans)
		return ans


class Solution:

	def par(self, ans, n, o, c, s):
		if o == n and c == n:
			ans.append(s)
			return
		if o < n:
			self.par(ans, n, o + 1, c, s + '(')
		if c < o:
			self.par(ans, n, o, c + 1, s + ')')

	def AllParenthesis(self, n):
		ans = []
		self.par(ans, n, 0, 0, '')
		return ans


class Solution:

	def AllParenthesis(self, n):
		ans = []

		def recursion(op, cl, res):
			if op < 0 or cl < 0:
				return
			if op == 0 and cl == 0:
				ans.append(res)
				return
			if op > cl:
				return
			recursion(op - 1, cl, res + '(')
			recursion(op, cl - 1, res + ')')
		recursion(n, n, '')
		return ans


class Solution:

	def AllParenthesis(self, n):
		result = []

		def backtrack(curr, left, right):
			if left == 0 and right == 0:
				result.append(curr)
			if left > 0:
				backtrack(curr + '(', left - 1, right + 1)
			if right > 0:
				backtrack(curr + ')', left, right - 1)
		backtrack('', n, 0)
		return result


class Solution:

	def AllParenthesis(self, n):
		openi = n
		close = n
		output = ''
		l = []

		def fun(openi, close, output, l):
			if openi == 0 and close == 0:
				l.append(output)
				return
			if openi != 0:
				oput1 = '('
				oput1 = output + oput1
				fun(openi - 1, close, oput1, l)
			if close > openi:
				oput2 = ')'
				oput2 = output + oput2
				fun(openi, close - 1, oput2, l)
			return l
		return fun(openi, close, output, l)


class Solution:

	def gen(self, arr, ch, n, open, close):
		if open > n:
			return
		if close == n:
			arr.append(ch)
			return
		self.gen(arr, ch + '(', n, open + 1, close)
		if open > close:
			self.gen(arr, ch + ')', n, open, close + 1)

	def AllParenthesis(self, n):
		ch = '('
		arr = []
		self.gen(arr, ch, n, 1, 0)
		return arr


class Solution:

	def helper(self, open1, close, prev):
		if open1 < 0 or close < 0:
			return
		if open1 == 0 and close == 0:
			self.temp.add(prev)
			return
		if open1 > 0:
			self.helper(open1 - 1, close, prev + '(')
		if close > open1:
			self.helper(open1, close - 1, prev + ')')

	def AllParenthesis(self, n):
		self.temp = set()
		self.helper(n, n, '')
		return list(self.temp)


class Solution:

	def recur(self, n, a, b, s, ans):
		if a == n and b == n:
			ans.append(s)
			return
		if a > n:
			return
		self.recur(n, a + 1, b, s + '(', ans)
		if a > b:
			self.recur(n, a, b + 1, s + ')', ans)

	def AllParenthesis(self, n):
		ans = []
		self.recur(n, 1, 0, '(', ans)
		return ans


class Solution:

	def AllParenthesis(self, n):
		arr = []
		res = []

		def solve(n, arr, openn, closen):
			if openn == closen == n:
				res.append(''.join(arr.copy()))
				return
			if closen < openn:
				arr.append(')')
				solve(n, arr, openn, closen + 1)
				arr.pop()
			if openn < n:
				arr.append('(')
				solve(n, arr, openn + 1, closen)
				arr.pop()
		solve(n, arr, 0, 0)
		return res


class Solution:

	def function(self, open, close, string, ans):
		if open == 0 and close == 0:
			ans.append(string)
			return
		if open != 0:
			s = string
			s = s + '('
			self.function(open - 1, close, s, ans)
		if close > open:
			s2 = string
			s2 = s2 + ')'
			self.function(open, close - 1, s2, ans)

	def AllParenthesis(self, n):
		open = n
		close = n
		string = ''
		ans = []
		self.function(open, close, string, ans)
		return ans


class Solution:

	def util(self, open, closed, tmp):
		if open < 0 or closed < 0:
			return
		if open == 0 and closed == 0:
			self.ans.add(tmp)
		if open > 0:
			self.util(open - 1, closed, tmp + '(')
		if open < closed:
			self.util(open, closed - 1, tmp + ')')

	def AllParenthesis(self, n):
		self.ans = set()
		self.util(n, n, '')
		return list(self.ans)


class Solution:

	def AllParenthesis(self, n):
		ans = []
		opt = ['(', ')']
		i = 0
		j = 0
		str = ''
		self.answer(str, i, j, n, ans)
		return ans

	def answer(self, str, i, j, n, ans):
		if i == n and j == n:
			ans.append(str)
		elif i == 0:
			str = str + '('
			self.answer(str, i + 1, j, n, ans)
		else:
			if j > i:
				return
			if i < n and j < n:
				self.answer(str + '(', i + 1, j, n, ans)
				self.answer(str + ')', i, j + 1, n, ans)
			elif i == n and j < n:
				self.answer(str + ')', i, j + 1, n, ans)
			else:
				self.answer(str + '(', i + 1, j, n, ans)


class Solution:

	def AllParenthesis(self, n):
		res = list()

		def p(s, pos=0, fo=0, fc=0):
			if pos > 2 * n - 1:
				res.append(s)
			else:
				if fo + 1 <= n:
					p(s + '(', pos + 1, fo + 1, fc)
				if fc + 1 <= fo:
					p(s + ')', pos + 1, fo, fc + 1)
		p('')
		return res


class Solution:

	def AllParenthesis(self, n):
		op = n
		close = n
		arr = []
		out = ''
		self.solve(op, close, arr, out)
		return arr

	def solve(self, op, close, arr, out):
		if op == 0 and close == 0:
			arr.append(out)
			return
		if op:
			out1 = out
			out1 = out1 + '('
			self.solve(op - 1, close, arr, out1)
		if close > op:
			out2 = out
			out2 = out + ')'
			self.solve(op, close - 1, arr, out2)


class Solution:

	def AllParenthesis(self, n):
		no = 0
		nc = 0
		s = ''
		ans = []

		def helper(n, no, nc, s, ans):
			l = len(s)
			if l == n * 2 and s[-1] == ')' and (nc == no):
				ans.append(s)
				return
			if nc == no:
				s += '('
				helper(n, no + 1, nc, s, ans)
				s = s[:l]
				return
			elif no > nc:
				if no < n:
					s += '('
					helper(n, no + 1, nc, s, ans)
					s = s[:-1]
				if nc < n:
					s += ')'
					helper(n, no, nc + 1, s, ans)
					s = s[:-1]
					return
		helper(n, no, nc, s, ans)
		return ans


class Solution:

	def AllParenthesis(self, n):

		def dfs(left, right, s):
			if len(s) == n * 2:
				res.append(s)
				return
			if left < n:
				dfs(left + 1, right, s + '(')
			if right < left:
				dfs(left, right + 1, s + ')')
		res = []
		dfs(0, 0, '')
		return res


class Solution:

	def AllParenthesis(self, n):
		stack = []
		res = []

		def gen(open, closed):
			if open == closed == n:
				res.append(''.join(stack))
				return
			if open < n:
				stack.append('(')
				gen(open + 1, closed)
				stack.pop()
			if closed < open:
				stack.append(')')
				gen(open, closed + 1)
				stack.pop()
		gen(0, 0)
		return res


class Solution:

	def AllParenthesis(self, n):
		res = []
		self.helper(n, n, res, '')
		return res

	def helper(self, open, close, res, op):
		if open == 0 and close == 0:
			res.append(op)
			return
		if open != 0:
			self.helper(open - 1, close, res, op + '(')
		if open < close:
			self.helper(open, close - 1, res, op + ')')


class Solution:

	def AllParenthesis(self, n):
		ans = []
		s = ''
		self.ans(s, ans, 0, 0, n)
		return ans

	def ans(self, s, ans, close, open, n):
		if close == n and open == n:
			ans.append(s)
			return
		else:
			if open < n:
				self.ans(s + '(', ans, close, open + 1, n)
			if close < n and close < open:
				self.ans(s + ')', ans, close + 1, open, n)


class Solution:

	def AllParenthesis(self, n):
		lst = []

		def helper(o, c, res, idx):
			if idx >= 2 * n:
				lst.append(res)
				return
			if o < n:
				helper(o + 1, c, res + '(', idx + 1)
			if c < o and c < n:
				helper(o, c + 1, res + ')', idx + 1)
		helper(0, 0, '', 0)
		return lst


class Solution:

	def AllParenthesis(self, n):
		li = []
		l = r = n
		i = 0
		stri = ''
		self.solve(li, stri, l, r, i, n)
		return li

	def solve(self, li, stri, l, r, i, n):
		if i == 2 * n - 1:
			li.append(stri + ')')
			return
		if l == 0:
			self.solve(li, stri + ')', l, r - 1, i + 1, n)
		elif l < r:
			self.solve(li, stri + '(', l - 1, r, i + 1, n)
			self.solve(li, stri + ')', l, r - 1, i + 1, n)
		elif l == r:
			self.solve(li, stri + '(', l - 1, r, i + 1, n)


class Solution:

	def AllParenthesis(self, n):
		l = []
		lt = n
		rt = n
		self.gen(lt, rt, n, 0, '', l)
		return l

	def gen(self, lt, rt, n, i, s, l):
		if i == 2 * n - 1:
			l.append(s + ')')
			return
		elif lt == rt:
			self.gen(lt - 1, rt, n, i + 1, s + '(', l)
		elif lt == 0:
			self.gen(lt, rt - 1, n, i + 1, s + ')', l)
		elif lt < rt:
			self.gen(lt, rt - 1, n, i + 1, s + ')', l)
			self.gen(lt - 1, rt, n, i + 1, s + '(', l)


class Solution:

	def AllParenthesis(self, n):

		def parenth(s, left, right):
			if len(s) == 2 * n:
				l.append(s)
				return
			if left < n:
				parenth(s + '(', left + 1, right)
			if right < left:
				parenth(s + ')', left, right + 1)
		l = []
		parenth('', 0, 0)
		return l


def brac(op, cl, n, st, res):
	if cl > op:
		return
	if op > n - 1 and cl > n - 1:
		res.append(st)
		return
	elif op > n - 1 and cl <= n - 1:
		while cl <= n - 1:
			st = st + ')'
			cl = cl + 1
		res.append(st)
		return
	else:
		brac(op + 1, cl, n, st + '(', res)
		brac(op, cl + 1, n, st + ')', res)

class Solution:

	def AllParenthesis(self, n):
		st = ''
		res = []
		brac(0, 0, n, st, res)
		return res


class Solution:

	def AllParenthesis(self, n):
		l = []
		s = ''
		self.parenthesis(n, 0, 0, s, l)
		return l

	def parenthesis(self, n, open, close, s, l):
		if open == n and close == n:
			l.append(s)
			return
		if open < n:
			self.parenthesis(n, open + 1, close, s + '(', l)
		if close < open:
			self.parenthesis(n, open, close + 1, s + ')', l)


class Solution:

	def __init__(self):
		self.all_paranthesis = list()

	def balanced_paranthesis(self, paranthesis: str) -> bool:
		if len(paranthesis) == 0 or paranthesis[0] == ')' or len(paranthesis) % 2 == 1:
			return False
		cnt = 1
		idx = 1
		while idx < len(paranthesis):
			if paranthesis[idx] == ')':
				if cnt == 0:
					return False
				cnt -= 1
			else:
				cnt += 1
			idx += 1
		return cnt == 0

	def generateAllBalancedParanthesis(self, open_brackets, closed_brackets, cnt, curr_str):
		if open_brackets == 0 and closed_brackets == 0:
			if cnt == 0:
				self.all_paranthesis.append(curr_str)
			return
		if open_brackets:
			self.generateAllBalancedParanthesis(open_brackets - 1, closed_brackets, cnt + 1, curr_str + '(')
		if closed_brackets and cnt > 0:
			self.generateAllBalancedParanthesis(open_brackets, closed_brackets - 1, cnt - 1, curr_str + ')')

	def AllParenthesis(self, n):
		if n == 0:
			return list()
		self.generateAllBalancedParanthesis(n - 1, n, 1, '(')
		return self.all_paranthesis


class Solution:

	def AllParenthesis(self, n):
		ans = []
		self.solve(ans, 0, 0, '', n)
		return ans

	def solve(self, ans, openn, close, output, n):
		if openn == n and close == n:
			ans.append(output)
			return
		if openn < n:
			self.solve(ans, openn + 1, close, output + '(', n)
		if close < openn:
			self.solve(ans, openn, close + 1, output + ')', n)


class Solution:

	def __init__(self):
		self.d = []

	def rec(self, a, c1, c2, c3):
		if c1 == 0 and c2 == 0:
			if c3 == 0:
				self.d.append(a)
			return
		if c1 > 0:
			self.rec(a + '(', c1 - 1, c2, c3 + 1)
		if c2 > 0 and c3 > 0:
			self.rec(a + ')', c1, c2 - 1, c3 - 1)

	def AllParenthesis(self, n):
		self.rec('', n, n, 0)
		return self.d


class Solution:

	def AllParenthesis(self, n):

		def helper(open, close, curr):
			if open == close == n:
				res.append(curr)
				return
			if open < n:
				curr += '('
				helper(open + 1, close, curr)
				curr = curr[:-1]
			if close < open:
				curr += ')'
				helper(open, close + 1, curr)
				curr = curr[:-1]
		res = []
		curr = ''
		helper(0, 0, curr)
		return res


class Solution:

	def AllParenthesis(self, n):
		return self.helper(n, 0, '')

	def helper(self, n, count, combo):
		if n == 0 and count == 0:
			return [combo]
		output = []
		if n:
			output += self.helper(n - 1, count + 1, combo + '(')
		if count:
			output += self.helper(n, count - 1, combo + ')')
		return output


def solve(open, closed, ans, s):
	if open == 0 and closed == 0:
		ans.append(s)
		return
	if open < closed:
		if open == 0:
			solve(open, closed - 1, ans, s + ')')
		else:
			solve(open - 1, closed, ans, s + '(')
			solve(open, closed - 1, ans, s + ')')
	else:
		solve(open - 1, closed, ans, s + '(')

class Solution:

	def AllParenthesis(self, n):
		ans = []
		solve(n, n, ans, '')
		return ans


def func(n, temp, ans, open, close):
	if open == n and close == n:
		ans.append(temp[:])
		return
	if open < n:
		func(n, temp + '(', ans, open + 1, close)
	if close < open:
		func(n, temp + ')', ans, open, close + 1)

class Solution:

	def AllParenthesis(self, n):
		ans = []
		func(n, '', ans, 0, 0)
		return ans


class Solution:

	def AllParenthesis(self, n):
		ans = []

		def backtrack(s, o, c, n):
			if len(s) == 2 * n:
				ans.append(''.join(s))
			if o < n:
				s.append('(')
				backtrack(s, o + 1, c, n)
				s.pop()
			if c < o:
				s.append(')')
				backtrack(s, o, c + 1, n)
				s.pop()
		s = []
		backtrack(s, 0, 0, n)
		return ans


class Solution:

	def AllParenthesis(self, n):
		res = []

		def solve(left, right, arr):
			if left == n and right == n:
				res.append(arr)
				return
			if right < left:
				arr1 = arr[:]
				arr += '('
				if left < n:
					solve(left + 1, right, arr)
				arr1 += ')'
				if right < n:
					solve(left, right + 1, arr1)
			elif left == right and left < n:
				arr += '('
				solve(left + 1, right, arr)
			else:
				return
		solve(0, 0, '')
		return res


class Solution:

	def AllParenthesis(self, n):
		l = []

		def f(s, left, right, l):
			if left == 0 and right == 0:
				l.append(s)
				return
			if left > 0:
				f(s + '(', left - 1, right, l)
			if right > 0 and left < right:
				f(s + ')', left, right - 1, l)
		f('', n, n, l)
		return l


class Solution:

	def AllParenthesis(self, n):
		res = list()

		def helper(opn, close, op, res):
			if opn == 0 and close == 0:
				res.append(op)
				return
			if opn >= close:
				helper(opn - 1, close, op + '(', res)
			else:
				if opn > 0:
					helper(opn - 1, close, op + '(', res)
				if close > 0:
					helper(opn, close - 1, op + ')', res)
		helper(n, n, str(), res)
		return res


class Solution:

	def util(self, n, res, ans, bo, bc):
		if bo == 0 and bc == 0:
			res.append(ans)
			return
		if bo > 0:
			temp = ans
			temp += '('
			self.util(n, res, temp, bo - 1, bc)
		if bc > bo:
			temp = ans
			temp += ')'
			self.util(n, res, temp, bo, bc - 1)

	def AllParenthesis(self, n):
		res = list()
		self.util(n, res, '', n, n)
		return res


class Solution:

	def __init__(self):
		self.answer = ()

	def AllParenthesis(self, n):
		return self.util('', n, n)

	def util(self, string, o, c):
		answer = []
		if o:
			answer.extend(self.util(string + '(', o - 1, c))
		if c > o:
			answer.extend(self.util(string + ')', o, c - 1))
		if o == 0 and c == 0:
			return [string]
		return answer


class Solution:

	def AllParenthesis(self, n):
		open = n
		close = n
		output = ''
		ls = []

		def solve(output, open, close):
			if open == 0 and close == 0:
				ls.append(output)
				return
			if open != 0:
				solve(output + '(', open - 1, close)
			if open < close:
				solve(output + ')', open, close - 1)
		solve(output, open, close)
		return ls


class Solution:

	def AllParenthesis(self, 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 res


class Solution:

	def solve(self, op, open, close, l):
		if close == 0:
			l.append(''.join(op))
			return
		op1 = []
		op2 = []
		if open == 0:
			op.append(')')
			self.solve(op, open, close - 1, l)
		elif open < close:
			op1 = op1 + op
			op2 = op2 + op
			op1.append('(')
			op2.append(')')
			self.solve(op1, open - 1, close, l)
			self.solve(op2, open, close - 1, l)
		else:
			op.append('(')
			self.solve(op, open - 1, close, l)

	def AllParenthesis(self, n):
		open = n
		close = open
		op = []
		l = []
		op.append('(')
		self.solve(op, open - 1, close, l)
		return l


class Solution:

	def AllParenthesis(self, n):
		result = []

		def backtrack(cb, ob, subset):
			if len(subset) == 2 * n:
				result.append(''.join(subset))
			else:
				if ob < n:
					subset.append('(')
					backtrack(cb, ob + 1, subset)
					subset.pop()
				if cb < ob:
					subset.append(')')
					backtrack(cb + 1, ob, subset)
					subset.pop()
		backtrack(0, 0, [])
		return result


class Solution:

	def AllParenthesis(self, n):

		def recurs(op, cl, ans, s):
			if op == 0 and cl == 0:
				ans.append(s)
				return
			else:
				if cl != 0:
					recurs(op, cl - 1, ans, s + ')')
				if op != 0:
					recurs(op - 1, cl + 1, ans, s + '(')
				return
		ans = []
		recurs(n, 0, ans, '')
		return ans