Generate Parentheses: Counting Backtrack

Generate Parentheses is the cleanest counting-backtrack problem in the catalog. The whole solution rides on two inequalities. Once you see them, the code writes itself.

The Problem

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

Example:

• Input: n = 3
• Output: ["((()))","(()())","(())()","()(())","()()()"]

Intuition

A partial string is extensible to a valid full string if and only if two facts hold: (1) we have not yet placed all n opens, and (2) we have not closed more than we have opened. Translate those facts into “we may add (” and “we may add )” branches, and every recursion path lands on a valid string with zero post-filtering. This is the brute-force tree pruned to exactly the Catalan-number worth of leaves.

Explanation with Example

n = 2. Start s='', opens=0, closes=0.

• Add (: s='(', opens=1, closes=0.
  • Add (: s='((', opens=2.
    • Cannot add (, opens==n. Add ): s='(()', closes=1.
      • Add ): s='(())'. Record.
  • Add ): s='()', closes=1.
    • Add (: s='()(', opens=2. Add ): s='()()'. Record.

Result: ["(())", "()()"].

                      ""
                     |
                   add (
                    "("
            +--------+--------+
          add (             add )
          "(("              "()"
            |                |
          add )            add (
          "(()"           "()("
            |                |
          add )            add )
          "(())"          "()()"

Branches that would break close<=open are pruned.

Code

Track the number of opens and closes used so far. Two simple rules: add ( while open < n, add ) while close < open.

def generate_parenthesis(n):
    result = []
    def backtrack(s, opens, closes):
        if len(s) == 2 * n:
            result.append(s)
            return
        if opens < n:
            backtrack(s + '(', opens + 1, closes)
        if closes < opens:
            backtrack(s + ')', opens, closes + 1)
    backtrack('', 0, 0)
    return result

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder cur, int opens, int closes, int n) {
        if (cur.length() == 2 * n) {
            result.add(cur.toString());
            return;
        }
        if (opens < n) {
            cur.append('(');
            backtrack(result, cur, opens + 1, closes, n);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (closes < opens) {
            cur.append(')');
            backtrack(result, cur, opens, closes + 1, n);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string cur;
        backtrack(result, cur, 0, 0, n);
        return result;
    }

private:
    void backtrack(vector<string>& result, string& cur, int opens, int closes, int n) {
        if ((int)cur.size() == 2 * n) {
            result.push_back(cur);
            return;
        }
        if (opens < n) {
            cur.push_back('(');
            backtrack(result, cur, opens + 1, closes, n);
            cur.pop_back();
        }
        if (closes < opens) {
            cur.push_back(')');
            backtrack(result, cur, opens, closes + 1, n);
            cur.pop_back();
        }
    }
};

Edge Cases

• n = 0: return [""], one empty string. Some implementations return an empty list; check the problem statement.
• n = 1: returns ["()"].
• Very large n: the answer count is the n-th Catalan number, which grows roughly as 4^n / n^(3/2). Memory becomes the bottleneck.

Complexity Analysis

• Time: O(4^n / sqrt(n)). The output size equals the n-th Catalan number, and each string is length 2n.
• Space: O(n) recursion depth, plus output size.

The brute force is O(2^(2n) * n) because of the filter step.

How to Explain It in an Interview

State the invariants first: “A prefix is extensible to a valid string if and only if opens <= n and closes <= opens.” From those two inequalities, the two recursive branches drop out. Mention that you’re avoiding the brute filter by encoding validity into the recursion itself. Note the Catalan complexity briefly to show you know it’s an optimal enumeration bound.

Related Problems

• Valid Parentheses (stack)
• Longest Valid Parentheses (DP)
• Remove Invalid Parentheses
• Valid Parenthesis String

Wrap up

Generate Parentheses is the canonical “constraint-driven backtracking” problem. The two-count invariant pattern reappears all over combinatorial search. Once you write it from scratch in two minutes, you’ve internalized a pattern that pays off in dozens of related problems.