Generate Parentheses

Examples

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

These are all 5 distinct ways to arrange 3 pairs of parentheses so that every opening bracket is properly matched and nested.

Input: n = 1
Output: ["()"]

Input: n = 2
Output: ["(())", "()()"]

Constraints

• 1 <= n <= 8

Approach

One way to solve this is to generate every possible sequence of 2n opening and closing brackets, and then filter down to the ones that happen to be valid. This works, but the vast majority of sequences it builds turn out to be invalid, so a lot of the work is wasted.

A much better way is to only ever build sequences that could still turn out valid, using backtracking. At each step, track how many opening brackets and how many closing brackets have been placed so far. You're allowed to add another opening bracket as long as you haven't used all n yet, and you're only allowed to add a closing bracket if there are currently more opening brackets placed than closing ones (otherwise you'd be closing something that was never opened). Once the string reaches length 2n, it's guaranteed to be one of the valid results.

Solutions

Brute Force — Generate All, Then Filter

Build every possible sequence of length 2n using just '(' and ')', and check each one for validity afterward, keeping only the valid ones.

function generateParenthesis(n) {
  const result = [];
  const total = 2 * n;

  function isValid(str) {
    let balance = 0;
    for (const char of str) {
      balance += char === "(" ? 1 : -1;
      if (balance < 0) return false;
    }
    return balance === 0;
  }

  function build(current) {
    if (current.length === total) {
      if (isValid(current)) result.push(current);
      return;
    }
    build(current + "(");
    build(current + ")");
  }

  build("");
  return result;
}

Time: O(2^(2n) * n) — every one of the 2^(2n) sequences is generated, and each is validated in O(n) · Space: O(n) recursion depth, plus the space to store the output

Optimal — Backtracking (Only Build Valid Prefixes)

Build the string one character at a time, but only add an opening bracket if fewer than n have been used, and only add a closing bracket if it wouldn't outnumber the opening brackets placed so far. Every complete string this produces is automatically valid.

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

  function backtrack(current, openCount, closeCount) {
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }
    if (openCount < n) {
      backtrack(current + "(", openCount + 1, closeCount);
    }
    if (closeCount < openCount) {
      backtrack(current + ")", openCount, closeCount + 1);
    }
  }

  backtrack("", 0, 0);
  return result;
}

Time: O(4^n / sqrt(n)) — the number of valid combinations (the nth Catalan number), each built in O(n) · Space: O(n) recursion depth, plus the space to store the output