‹ DS&A interview · Socratic
DSA · Backtracking · #79

Generate Parentheses

Module 52 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given `n` pairs of parentheses, write a function `generateParenthesis(n)` that returns **all** combinations of well-formed (balanced) parentheses. A string of parentheses is well-formed if every opening bracket `(` has a matching closing bracket `)` and brackets are correctly nested. The order of the returned strings does not matter.

Examples
  • n = 1 → ["()"] — Only one valid arrangement for a single pair.
  • n = 3 → ["((()))","(()())","(())()","()(())","()()()"] — All 5 well-formed strings (the 3rd Catalan number).
  • n = 2 → ["(())","()()"]
Constraints
  • · 1 <= n <= 8
  • · The result has exactly C(n) strings, where C is the nth Catalan number.
  • · Returned order is not significant.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.