Generate All Well-Formed Parentheses

medium backtracking string

Problem

Return every well-formed parenthesis string using exactly n pairs.

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(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 generate(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> generate(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> generate(int n) {
    string s; back(s, n, n);
    return out;
}

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