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

        

Dry Run