Skip to main content

18. Generate Parentheses

mediumAsked at Grab

Generate all well-formed parenthesis strings of length 2n — Grab uses this as a backtracking fluency check.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Constraints

  • 1 <= n <= 8

Examples

Example 1

Input
n = 3
Output
["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input
n = 1
Output
["()"]

Approaches

1. Generate all and filter

Enumerate every 2n-length string of ( and ) and keep the valid ones.

Time
O(2^(2n) * n)
Space
O(n)
// recursion to build all 2^(2n) candidates
// filter by stack-validity check
// quickly explodes past n=6

Tradeoff:

2. Backtracking with counts

Recurse tracking open and close counts; add '(' if open < n, add ')' if close < open.

Time
O(C(n))
Space
O(n)
function generateParenthesis(n) {
  const out = [];
  const go = (cur, open, close) => {
    if (cur.length === 2 * n) { out.push(cur); return; }
    if (open < n) go(cur + '(', open + 1, close);
    if (close < open) go(cur + ')', open, close + 1);
  };
  go('', 0, 0);
  return out;
}

Tradeoff:

Grab-specific tips

Grab interviewers expect you to prune in the recursion, not after — frame as generating valid bracket configurations for SEA multi-service receipt grammars.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Generate Parentheses and other Grab interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →