Generate Parentheses

medium backtracking string

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Track open (number of '(' still allowed) and close (number of ')' still allowed). Append '(' if open > 0; append ')' if close > open, i.e. there's an unmatched '('. When both counters hit zero, the string is balanced — emit it. The number of valid strings is the n-th Catalan number.

Inputn = 3

Output((())) (()()) (())() ()(()) ()()()

Five strings — Catalan(3) = 5.

def generate_parentheses(n):
    out = []
    def back(s, open_, close_):
        if not open_ and not close_:
            out.append(s); return
        if open_:
            back(s + "(", open_ - 1, close_)
        if close_ > open_:
            back(s + ")", open_, close_ - 1)
    back("", n, n)
    return out

function generateParentheses(n) {
  const out = [];
  function back(s, open, close) {
    if (!open && !close) { out.push(s); return; }
    if (open) back(s + "(", open - 1, close);
    if (close > open) back(s + ")", open, close - 1);
  }
  back("", n, n);
  return out;
}

List<String> out = new ArrayList<>();
public List<String> generateParentheses(int n) {
    back(new StringBuilder(), n, n);
    return out;
}
void back(StringBuilder sb, int open, int close) {
    if (open == 0 && close == 0) { out.add(sb.toString()); return; }
    if (open > 0) {
        sb.append('('); back(sb, open - 1, close); sb.deleteCharAt(sb.length() - 1);
    }
    if (close > open) {
        sb.append(')'); back(sb, open, close - 1); sb.deleteCharAt(sb.length() - 1);
    }
}

vector<string> out;
void back(string& s, int open, int close) {
    if (open == 0 && close == 0) { out.push_back(s); return; }
    if (open) { s.push_back('('); back(s, open - 1, close); s.pop_back(); }
    if (close > open) { s.push_back(')'); back(s, open, close - 1); s.pop_back(); }
}
vector<string> generateParentheses(int n) {
    string s; back(s, n, n);
    return out;
}

Explanation

We build valid parenthesis strings one character at a time, and the trick is to never let the string go invalid. By only adding a bracket when it keeps the string well-formed, every leaf of the search is automatically a valid answer.

We track two counters: open is how many ( we may still add, and close is how many ) we may still add. Both start at n.

The two rules are simple. We may add ( whenever open > 0 (we still have opens to spend). We may add ) only when close > open, which means there is an unmatched ( waiting to be closed. That single condition is what guarantees the string never has a stray closing bracket.

When both counters reach 0, the string uses all n pairs and is balanced, so we record it.

Example: n = 3. Starting empty we can only add (; following the rules the search produces ((())), (()()), (())(), ()(()), ()()() — exactly Catalan(3) = 5 strings.

Time: O(4ⁿ / √n) (Catalan) Space: O(n) recursion