DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Generate Parentheses

mediumRecursion

Problem statement

Given a number n, return every string made of exactly n opening brackets ( and n closing brackets ) that is balanced. A string is balanced when, reading left to right, the number of ) seen never exceeds the number of ( seen, and the two counts are equal at the end.

The strings can be returned in any order.

Examples

Example 1

Input: n = 2

Output: ["(())", "()()"]

Example 2

Input: n = 3

Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Explanation: Five balanced strings of length 6.

Hints

Approach

Only ever make a move that can still lead to a balanced string. Track how many ( and ) have been placed.

  1. dfs(open, close): if the string has length 2n, record it.
  2. If open < n, add ( and recurse with open + 1.
  3. If close < open, add ) and recurse with close + 1.
  4. Undo each addition after its recursive call.

Rule 3 guarantees the running depth never goes negative, and rule 2 guarantees the counts end equal, so every leaf is a valid answer and nothing is filtered afterwards. The number of results is the n-th Catalan number, which grows roughly like 4^n / n^1.5.

ComplexityTime O(4^n / √n)Space O(n) besides the output
Python
class Solution:
def generateParenthesis(self, n: int) -> list[str]:
result, path = [], []
def dfs(open_: int, close: int) -> None:
if len(path) == 2 * n:
result.append("".join(path))
return
if open_ < n: # room for another opener
path.append("(")
dfs(open_ + 1, close)
path.pop()
if close < open_: # a closer has something to match
path.append(")")
dfs(open_, close + 1)
path.pop()
dfs(0, 0)
return result

Follow-up questions

  • Given one string of brackets, remove the fewest characters to make it balanced.
  • Generate strings with two bracket types, () and [], that are correctly nested.

Frequently asked questions

A ) is only valid if there is an unmatched ( before it. The number of unmatched openers is exactly open - close, so it must be positive before you close one.

The count for n pairs is the Catalan number: 1, 2, 5, 14, 42 for n = 1 to 5. It grows much more slowly than 2^(2n), which is why pruning during generation beats filtering afterwards.

Balanced nesting is what config and template validators check: braces in JSON or HCL, block tags in Jinja or Helm templates. Generating valid nestings is also how you build test inputs for such a parser.