0022-generate-parentheses¶
Try it on leetcode
Description¶
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1 Output: ["()"]
Constraints:
1 <= n <= 8
Solution(Python)¶
class Solution:
def generateParenthesis(self, n: int) -> list[str]:
#
def isvalid(paren):
stack = []
open_count = 0
for brac in paren:
if brac == "(":
open_count += 1
stack.append(brac)
else:
if not stack:
return False
stack.pop()
return open_count <= n
def backtrack(i,n, paren):
if i >= 2* n:
res.append("".join(paren))
return
for brac in ['(',')']:
paren.append(brac)
if isvalid(paren):
backtrack(i+1, n, paren)
paren.pop()
res = []
backtrack(0, n, [])
return res