Generate Parentheses

BACKTRACKING · MEDIUM

Builds on Day 9: Recursion & the Call Stack

Both solutions below are recursive backtracking; read that lesson first if the call stack mental model is still new. It also pairs well with Day 17’s Valid Parentheses lesson — that problem CHECKS balance on a given string; this one GENERATES strings that are balanced.

The problem

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

Solution 1: Brute force — generate everything, filter at the end

Build every possible string of length 2n from ( and ) — a full binary decision tree, adding either character unconditionally at every position — then check each completed string for validity, using the same running-balance idea as Day 17’s Valid Parentheses check.

function isValidParens(s) {
  let bal = 0;
  for (const ch of s) { bal += ch === '(' ? 1 : -1; if (bal < 0) return false; }
  return bal === 0;
}
function generateParenthesisBrute(n) {
  const len = 2 * n, result = [];
  function dfs(path) {
    if (path.length === len) { if (isValidParens(path)) result.push(path); return; }
    dfs(path + '(');
    dfs(path + ')');
  }
  dfs('');
  return result;
}

Line by line:

• dfs(path) unconditionally branches into BOTH path + "(" and path + ")" at every position — nothing rules either choice out.
• The base case only triggers once path.length === 2n — by then, the tree has already fully explored every one of the 2^(2n) possible strings.
• isValidParens is the exact same running-balance idea as Day 17’s Valid Parentheses check — but here it’s applied AFTER the string is fully built, instead of catching an invalid state early.

Interactive visualization

Brute force: n=2 — build every 2n-length string unconditionally, then filter

Press Play or Step to begin.

call stack depth: 0

Step 0 / 0

▶ PlayStep ⏭⟲ Reset

This animation traces n=2 (78 steps — even this tiny case shows real waste) — a case verified above.

Complexity

Aspect	Complexity
Time	O(2^(2n) × n)
Space	O(n) recursion depth

Solution 2: Optimal — only add a paren if it can’t possibly break validity

Track how many ( and ) have been placed so far. Only add ( if there’s still room (open < n), and only add ) if there’s an unmatched ( to pair it with (close < open) — every string this produces is guaranteed valid by construction, with no filtering step needed.

function generateParenthesisOptimal(n) {
  const result = [];
  function dfs(path, open, close) {
    if (path.length === 2 * n) { result.push(path); return; }
    if (open < n) dfs(path + '(', open + 1, close);
    if (close < open) dfs(path + ')', open, close + 1);
  }
  dfs('', 0, 0);
  return result;
}

Line by line:

• open and close track how many of each character have been placed so far in the current path.
• open < n guards adding ( — never place more than n open parens total.
• close < open (not close < n) is the key guard — a ) is only safe if there’s an unmatched ( still open to pair it with; comparing against open, not n, is what guarantees the string never goes unbalanced at any prefix.
• No validity check is needed at the base case — the two guards already make it structurally impossible to construct an invalid string.

Interactive visualization

Optimal: n=2 — only add a paren if it can't break validity

Press Play or Step to begin.

call stack depth: 0

Step 0 / 0

▶ PlayStep ⏭⟲ Reset

This animation traces n=2 — a case verified above.

Complexity

Aspect	Complexity
Time	Bounded by the n-th Catalan number (much smaller than 2^(2n))
Space	O(n) recursion depth

Complexity comparison

Solution	Strings explored
Brute force (generate-then-filter)	2^(2n) — most invalid
Optimal (constrained construction)	Bounded by the n-th Catalan number — all valid

This IS a real asymptotic improvement, not just a constant-factor speedup — the brute-force version explores every one of the 2^(2n) possible strings regardless of validity, while the optimal version only ever explores paths that could still become valid, a set bounded by the much smaller Catalan numbers.

Interview corner

Q: How would you count the valid combinations without generating all of them?

• The count of valid parenthesizations for n pairs is exactly the n-th Catalan number, C(2n, n) / (n + 1).
• No backtracking is needed at all if only the COUNT is required — it’s a pure math formula.

Q: How would you extend this to support multiple bracket types, like generating valid combinations of both () and []?

• Track a STACK of currently-open bracket types instead of two plain counters.
• A closing bracket is only valid if it matches whatever type is on TOP of that stack (last-opened, first-closed) — the same LIFO idea Day 17’s Valid Parentheses checker uses, just generating instead of validating.

Q: What’s the recursion depth for this problem?

• Always exactly 2n — the string grows by exactly one character per call until it reaches length 2n.
• This is shallower and more predictable than Combination Sum or Permutations, where depth depends on the specific input values.

Q: Trick question — what does this log?

const fns = [];
for (var i = 0; i < 3; i++) { fns.push(() => i); }
console.log('var:', fns.map(f => f()));
const fns2 = [];
for (let j = 0; j < 3; j++) { fns2.push(() => j); }
console.log('let:', fns2.map(f => f()));

• With var: [3, 3, 3] — every arrow function closes over the SAME i variable, which is 3 by the time any of them actually runs, since var is function-scoped, not block-scoped.
• With let: [0, 1, 2] — let creates a FRESH binding of the loop variable for each iteration, so each closure captures its own separate value.
• This is a standalone JavaScript fundamental, not a bug in the recursive code shown above — the loops on this page are synchronous, so var vs let wouldn’t actually change their behavior here. It matters the moment a loop captures a variable in a callback that runs LATER (a setTimeout, an event handler, a .then()) — exactly the situation this trick demonstrates.

Quiz

1. Why does the brute-force solution generate exactly 2^(2n) strings before filtering?

At each of the 2n positions it tries both ‘(’ and ‘)’ unconditionally, so the full binary decision tree has 2^(2n) leaves, valid or notBecause it sorts every string before checking validityIt generates exactly the n-th Catalan number of strings, same as the optimal solution

2. What do the open and close counters track in the optimal solution?

How many ‘(’ and ‘)’ characters have been placed so far in the current pathThe total number of valid strings found so farThe current recursion depth

3. Why is close < open (not close < n) the correct condition for adding ‘)’?

A ‘)’ is only safe to add if there’s an unmatched ‘(’ still open to pair it with — comparing close against open is what guarantees the string never goes unbalancedBoth conditions are equivalent — either one worksclose < n would allow more valid combinations to be found

4. Why does the optimal solution never need a validity check at the end, unlike the brute-force one?

Its two guard conditions (open<n, close<open) make it structurally impossible to ever construct an invalid string in the first placeIt does need one — the solution shown is missing that checkValidity is checked once at the very start instead

5. Both solutions produce the same 5 valid strings for n=3 — what’s the real difference between them?

The brute-force solution wastes time constructing and discarding invalid strings; the optimal solution only ever explores paths that could still become validThere’s no real difference — both explore the exact same number of stringsThe optimal solution produces the strings in a different, non-equivalent order that changes the answer