Generate Parentheses

The problem. Given n, return every string of n pairs of parentheses that is well-formed — each ) closes an earlier ( and every ( is closed — in any order.

Example

n = 1  ->  ["()"]
n = 2  ->  ["(())", "()()"]
n = 3  ->  ["((()))", "(()())", "(())()", "()(())", "()()()"]

The idea: only make choices that keep the prefix valid

Generating all 2²ⁿ strings of brackets and keeping the valid ones works, but most of them are hopeless from an early point — anything starting with ), for example. Backtracking can prune those branches before they grow: build the string one bracket at a time and only allow a move that keeps the prefix fixable.

Two counts are enough. A ( is allowed while fewer than n have been used. A ) is allowed only while it has something to close — while close < open. With those rules every prefix stays valid, so every string that reaches length 2n is an answer, and nothing needs checking at the end.

1. Brute force: every bracket string, then filter

1function generateParenthesis(n) {2  const result = [];3  const valid = (s) => {4    let balance = 0;5    for (const ch of s) {6      balance += ch === "(" ? 1 : -1;7      if (balance < 0) return false;          // a ')' with nothing to close8    }9    return balance === 0;10  };11  const all = (s) => {                        // every string of '(' and ')' of length 2n12    if (s.length === 2 * n) {13      if (valid(s)) result.push(s);14      return;15    }16    all(s + "(");17    all(s + ")");18  };19  all("");20  return result;21}

Time O(2²ⁿ · n), space O(n) beyond the output. For n = 8 that's 65,536 strings to build and check, to keep 1,430.

2. Backtracking with two counts

1function generateParenthesis(n) {2  const result = [];3  const path = [];4  const build = (open, close) => {            // how many '(' and ')' are used so far5    if (path.length === 2 * n) {6      result.push(path.join(""));7      return;8    }9    if (open < n) {                           // a '(' is allowed while some are left10      path.push("(");11      build(open + 1, close);12      path.pop();13    }14    if (close < open) {                       // a ')' only if it closes something15      path.push(")");16      build(open, close + 1);17      path.pop();18    }19  };20  build(0, 0);21  return result;22}

Time O(4ⁿ / √n), space O(n) beyond the output. The number of answers is the n-th Catalan number, about 4ⁿ / (n^1.5 · √π), and since no branch dead-ends, the work is that number times the length 2n.

Comparing the approaches

The lesson of this problem is pruning: the rules about when a choice is allowed cut the search down to exactly the answers.

Edge cases to test

Variations