9.7

Idea
Keep two counters while building a string: the number of open parentheses still available (open) and the number of closing parentheses that can legally be placed (close, i.e. those that match an already opened one). At each step you may
1. add “(” if open > 0
2. add “)” if close > open (to maintain validity).
When both counters reach 0 the string is complete.

Pseudocode
generate(n):
  res ← []
  backtrack(seq="", open=n, close=n)

  backtrack(seq, open, close):
    if open = 0 and close = 0: add seq to res; return
    if open > 0: backtrack(seq + "(", open − 1, close)
    if close > open: backtrack(seq + ")", open, close − 1)

Python implementation

def generate_parentheses(n): res = [] def backtrack(seq, open_left, close_left): if not open_left and not close_left: res.append(seq) return if open_left: backtrack(seq + "(", open_left - 1, close_left) if close_left > open_left: backtrack(seq + ")", open_left, close_left - 1) backtrack("", n, n) return res # example print(generate_parentheses(3)) # ['((()))', '(()())', '(())()', '()(())', '()()()']

Complexity
There are C_n = (1/(n+1))·binom(2n,n) Catalan sequences; the algorithm visits all of them, so
• Time ≈ O(C_n)
• Space ≈ O(n) for the recursion stack (output excluded).

Back to Chapter 9