Problem Statement & Examples

A parenthesis string is well-formed if and only if every opening bracket ( has a corresponding closing bracket ), and at no point reading from left to right does the count of closing brackets exceed opening brackets.

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

Input: n = 1
Output: ["()"]

Mathematical Combinatorics: Catalan Numbers & Dyck Paths

How many valid combinations exist for a given n? The total count of well-formed parentheses strings of length 2n is given by the n-th Catalan Number ($C_n$):

In discrete mathematics, this problem is equivalent to counting Dyck Paths: monotonic lattice paths on a 2D grid from $(0, 0)$ to $(2n, 0)$ consisting of steps $(1, 1)$ (representing an open parenthesis) and $(1, -1)$ (representing a close parenthesis) that never dip below the horizontal x-axis ($y = 0$). Any path that drops below the axis corresponds to an illegal prefix where closing parentheses outnumber opening parentheses.

For small values of n, the sequence grows as follows:

• n = 1: $C_1 = 1$ ("()")
• n = 2: $C_2 = 2$ ("(())", "()()")
• n = 3: $C_3 = 5$ (5 combinations)
• n = 4: $C_4 = 14$
• n = 8: $C_8 = 1,430$

Asymptotically, $C_n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}$. This mathematical bound confirms that any algorithm generating all combinations must take at least $O\left(\frac{4^n}{\sqrt{n}}\right)$ time.

State Machine & Backtracking Tree

To generate only valid combinations and avoid exploring dead-end permutations, we enforce two invariant rules at every recursive step:

1. Rule 1 (Add Open): We can append ( whenever the count of open brackets placed so far is strictly less than n (open < n).
2. Rule 2 (Add Close): We can append ) if and only if the count of close brackets is strictly less than open brackets (close < open).

Iterative Dynamic Programming Decomposition

While backtracking DFS is the most intuitive and memory-efficient approach, understanding the Dynamic Programming formulation deepens algebraic mastery of the problem. Every non-empty well-formed parenthesis string $S$ can be factored uniquely as:

where $A$ is a well-formed parenthesis string of $k$ pairs ($0 le k le n - 1$), and $B$ is a well-formed parenthesis string of $(n - 1 - k)$ pairs. This allows bottom-up table building:

• For $n = 0$: $DP[0] = [, "" ,]$
• For $n = 1$: $k = 0 implies "(" + DP[0] + ")" + DP[0] = [, "()" ,]$
• For $n = 2$: $k = 0 implies "(" + DP[0] + ")" + DP[1] = [, "()()" ,]$; $k = 1 implies "(" + DP[1] + ")" + DP[0] = [, "(())" ,]$

While DP requires additional memory to store intermediate subproblem lists, it eliminates recursion stack overhead and showcases the direct isomorphism between grammar production rules and dynamic programming.

Modern C++20 Implementation (Zero-Allocation Buffer Reuse)

In early implementations, recursive algorithms frequently pass string copies by value or utilize std::function closures, incurring unnecessary heap allocations. The optimal production implementation uses a mutable reference buffer with push_back and pop_back, avoiding string copying until a valid leaf is reached:

#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> generateParenthesis(int n) {
        std::vector<std::string> result;
        std::string current;
        current.reserve(2 * n); // Pre-allocate buffer capacity
        
        backtrack(n, 0, 0, current, result);
        return result;
    }

private:
    void backtrack(int n, int openCount, int closeCount, 
                   std::string& current, std::vector<std::string>& result) {
        // Base case: string has reached maximum length (2 * n)
        if (static_cast<int>(current.length()) == 2 * n) {
            result.push_back(current);
            return;
        }

        // Branch 1: Add opening parenthesis if quota remains
        if (openCount < n) {
            current.push_back('(');
            backtrack(n, openCount + 1, closeCount, current, result);
            current.pop_back(); // Backtrack state
        }

        // Branch 2: Add closing parenthesis if valid
        if (closeCount < openCount) {
            current.push_back(')');
            backtrack(n, openCount, closeCount + 1, current, result);
            current.pop_back(); // Backtrack state
        }
    }
};

int main() {
    Solution solver;
    int n = 3;
    std::vector<std::string> solutions = solver.generateParenthesis(n);

    std::cout << "Total solutions for n = " << n << ": " << solutions.size() << "\n";
    for (const auto& s : solutions) {
        std::cout << "  " << s << "\n";
    }

    return 0;
}

Production Engineering: Compiler Parsers & AST Tokenizers

The logic underpinning parenthesis generation is not merely an interview parlor trick; it is the fundamental core of syntax analyzers in compilers and build tools:

• HTML / JSX Tag Balancing: When compilers like Babel or SWC parse JSX elements, they track opening and closing tags in a LIFO structure directly analogous to parentheses validation. An unclosed <div> or mismatched closing tag triggers a syntax error through identical invariant checks.
• Mathematical Expression Evaluators: In Dijkstra's Two-Stack Shunting-Yard algorithm for converting infix expressions to Reverse Polish Notation (RPN), matching parentheses dictate operator precedence and subexpression tree evaluation.

Complexity Analysis