A code generator for a policy DSL had to emit every legal wrapping of n pairs around a rule body — nested and sequential. The intern mapped each bitmask of length 2n onto ( and ), then ran a validity pass. n = 3 is 64 complete strings and looked cheap. n = 8 is 65,536, and most of those strings were already illegal at the first extra ).

Generate Parentheses asks for every well-formed string of n pairs. Enumerating all 2^(2n) bitmasks and filtering uses that and still builds prefixes a checker would reject on the first extra close.

This is an interview writeup, not a backtracking lecture. That post owns the search shape. The stack post owns LIFO. Here we only care about two counters so a partial string stays legal: opens still unused, opens still unmatched.

The problem

Given an int n, return all strings that use exactly n pairs of well-formed (). Order of the list does not matter.

n = 1  →  ["()"]
n = 3  →  ["((()))", "(()())", "(())()", "()(())", "()()()"]

Note: Checking one string is Valid Parentheses. This prompt asks you to emit every legal wrapping, not to accept or reject a given one.

Every bitmask, then a checker, is the honest brute force

Each of the 2n positions is ( or ). Walk every integer mask in 0 .. 2^(2n) - 1, decode bits into a string, and keep the well-formed ones — reuse the Valid Parentheses stack checker, or the running count that post already named: balance never goes negative and ends at zero. You still finish strings that were dead at index 0.

List<String> generateParenthesisBrute(int n) {
    List<String> out = new ArrayList<>();
    int len = 2 * n;
    int limit = 1 << len;
    char[] buf = new char[len];
    for (int mask = 0; mask < limit; mask++) {
        for (int i = 0; i < len; i++) {
            buf[i] = ((mask >> i) & 1) == 0 ? '(' : ')';
        }
        if (wellFormed(buf)) {
            out.add(new String(buf));
        }
    }
    return out;
}

boolean wellFormed(char[] s) {
    int bal = 0;
    for (int i = 0; i < s.length; i++) {
        bal += s[i] == '(' ? 1 : -1;
        if (bal < 0) {
            return false;
        }
    }
    return bal == 0;
}

At n = 3 this is 64 scans. At n = 8 you paid for 65,536 complete strings so a filter could throw most of them away: could this prefix still become n well-formed pairs?

Recurse on openUsed and closeUsed

Grow one character at a time. openUsed is how many ( you have placed. closeUsed is how many ). Length is openUsed + closeUsed.

  • Place ( if openUsed < n.
  • Place ) if closeUsed < openUsed.
  • At length 2n, record the path. The two rules already guarantee the leaf is well-formed — you do not run a checker.

A close with closeUsed == openUsed would be the extra ) the intern’s filter found too late. An open with openUsed == n would be an (n+1)st pair the prompt did not ask for.

Walk n = 2. The intern still generated 16 bitmasks; this tree has two leaves.

n = 2. '(' if openUsed < 2. ')' if closeUsed < openUsed.

""              open=0 close=0   ')' refused
  "("           1,0
    "(("        2,0              '(' refused (openUsed == n)
      "(()"     2,1
        "(())"  2,2              record
    "()"        1,1              ')' refused (closeUsed == openUsed)
      "()("     2,1
        "()()"  2,2              record

You never built )( or ()). Those prefixes fail closeUsed < openUsed the moment the extra ) is offered, so they are not a string you later throw away.

The Java is that walk. Index k is the next slot; a sibling overwrites it.

List<String> generateParenthesis(int n) {
    List<String> out = new ArrayList<>();
    char[] path = new char[2 * n];
    grow(0, 0, n, path, out);
    return out;
}

void grow(int openUsed, int closeUsed, int n, char[] path, List<String> out) {
    int k = openUsed + closeUsed;
    if (k == 2 * n) {
        out.add(new String(path));
        return;
    }
    if (openUsed < n) {
        path[k] = '(';
        grow(openUsed + 1, closeUsed, n, path, out);
    }
    if (closeUsed < openUsed) {
        path[k] = ')';
        grow(openUsed, closeUsed + 1, n, path, out);
    }
}

Time is the pruned tree — one visit per legal prefix, one O(n) copy per leaf. Space is O(n) for the path (depth 2n), plus the list you return. Do not quote 2^(2n) as the intended bill; that is the bitmask generator.

Note: A close is legal only while closeUsed is strictly less than openUsed. That is the prune. openUsed < n is the budget. Swap them and you emit )( or you never finish n pairs.

What interviewers usually poke next

  • n = 0. Ask whether it is in scope. The usual answer is one empty string: zero pairs is well-formed.
  • Count the strings, do not return them. Same tree; increment at the leaf instead of copying. The count is the Catalan number C_n. Naming it is enough; do not derive the formula unless they ask.
  • Multiple bracket types. Checking one mixed string is Valid Parentheses again. Generating every mixed wrapping is a different prompt; do not rewrite this method into that one.
  • Iterative. An explicit stack of partial strings — each frame (path, openUsed, closeUsed) — is the same two rules without recursion. Same prune. Do not invent a third counter.

You are done with this problem when you can refuse ) at the empty prefix, refuse a third ( at n = 2, walk (()) and ()() out loud, and say why the bitmask filter paid for strings the two counters never build.