Skip to content

22. Generate Parentheses

String Dynamic Programming Backtracking

Problem - Generate Parentheses

Medium

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []

        def backtrack(current: str, num_open: int, num_closed: int):
            if len(current) == n * 2: # last bracket
                result.append(current)
                return
            if num_open < n:
                backtrack(current + '(', num_open + 1, num_closed)
            if num_open > num_closed:
                backtrack(current + ')', num_open, num_closed + 1)

        backtrack("", 0, 0)
        return result

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 18 MB (69.67%)