Generate Parentheses

1. Define the problem

Given n pairs of parentheses, generate all combinations of well-formed parentheses. Use backtracking that tracks how many opens and closes have been placed so far: try adding an open paren whenever there's still one available, try adding a close paren only when it wouldn't outnumber the opens, and undo each character after recursing so the other option can be tried in its place.

Constraints

1 ≤ n ≤ 8

Example

Inputn = 3

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

Explanation These are the 5 distinct ways to arrange 3 well-formed pairs of parentheses.

2. Know the words first

In plain terms

Well-formed: Every closing parenthesis has a matching opening one before it, and the string ends with none left unmatched — like '(())' but not '())(' .

3. Visualize the solution

Track opens and closes used, undo to try the other option

Statustry

Place "(" (0 opens → 1): path="(".

What happens in this step

path = "(", open=1, close=0
choice: place '(' (open 0 < n=3), try continuing

backtrack(0,0) sees open(0) < n(3), so it pushes '(' and recurses into backtrack(1,0). The close branch isn't checked yet at this level since it's only tried after the open branch returns.

Step 1 of 5

Steps to visualize

Try adding an open paren whenever fewer than n have been placed so far.
Try adding a close paren only when fewer closes than opens have been placed — otherwise the string would go invalid.
Once 2n characters have been placed, record the path as one combination.
Undo the last character placed so the other option can be tried at this position.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track opens and closes used, undo to try the other option

Statustry

Place "(" (0 opens → 1): path="(".

What happens in this step

path = "(", open=1, close=0
choice: place '(' (open 0 < n=3), try continuing

backtrack(0,0) sees open(0) < n(3), so it pushes '(' and recurses into backtrack(1,0). The close branch isn't checked yet at this level since it's only tried after the open branch returns.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function generateParenthesis(n) {
  const result = [];
  const path = [];

  function backtrack(open, close) {
    if (path.length === 2 * n) {
      result.push(path.join(''));
      return;
    }

    if (open < n) {
      path.push('(');
      backtrack(open + 1, close);
      path.pop();
    }

    if (close < open) {
      path.push(')');
      backtrack(open, close + 1);
      path.pop();
    }
  }

  backtrack(0, 0);
  return result;
}

Time: O(4^n / sqrt(n))
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`n = 3`	`["((()))","(()())","(())()","()(())","()()()"]`	example from the docstring
`n = 1`	`["()"]`	smallest valid input, a single pair
`n = 2`	`["(())","()()"]`	two pairs, only two arrangements possible
`n = 4`	`14 combinations (the 4th Catalan number)`	larger input where the branching factor grows further

Generate Parentheses