Generate Parentheses

Practice Link

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

Example:

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

Key Idea#

At every position in the string we have at most two choices — add ( or add ) — but only if it keeps the string on track to be valid. Rather than generating all 2²ⁿ combinations and filtering, we enforce the validity constraints during construction to prune invalid branches early.

Intuition#

Two counters drive the recursion:

Rules that keep a prefix valid:

1. We can add ( as long as opened < n — we haven't used up all open brackets yet.
2. We can add ) as long as closed < opened — we only close what's already open.

When temp.size() == 2 * n, every open bracket has been matched, so the string is complete and valid — add it to results.

These two rules completely eliminate invalid states, so every leaf of the recursion tree is a valid answer. No filtering needed.

Solution#

class Solution {
public:
    void generateParenthesisUtil(string temp, vector<string> &result,
                                  int numberOfOpened, int numberOfClosed, int n) {
        if (temp.size() == 2 * n) {
            result.push_back(temp);
            return;
        }

        if (numberOfOpened < n) {
            generateParenthesisUtil(temp + '(', result,
                                     numberOfOpened + 1, numberOfClosed, n);
        }
        if (numberOfClosed < numberOfOpened) {
            generateParenthesisUtil(temp + ')', result,
                                     numberOfOpened, numberOfClosed + 1, n);
        }
    }

    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string temp = "";
        generateParenthesisUtil(temp, result, 0, 0, n);
        return result;
    }
};

Trace for n = 2:

""
├─ "("          (opened=1, closed=0)
│  ├─ "(("      (opened=2, closed=0)
│  │  └─ "(()" (opened=2, closed=1)
│  │     └─ "(())" ✓
│  └─ "()"      (opened=1, closed=1)
│     └─ "()()" (opened=2, closed=1... wait, here opened=1 still)
│        → "()((" → ... → "()()" ✓

Output: ["(())", "()()"]

Time Complexity: O(4ⁿ / √n) — the nth Catalan number bounds the output size; each string takes O(n) to build.

Space Complexity: O(n) — recursion depth is at most 2n (one frame per character added).

Follow Up#

Can you do it iteratively?#

Yes — use an explicit stack that stores (current_string, opened, closed) triples instead of the call stack. The logic mirrors the recursive version exactly; it's more verbose but avoids stack-overflow risk for very large n.

What is the Catalan number connection?#

The number of valid parenthesizations of n pairs is the nth Catalan number: C(n) = C(2n, n) / (n + 1). For n = 3 that's 5; for n = 4 it's 14. Catalan numbers appear in many combinatorics problems — BST structures, triangulations, ballot sequences — all share the same recursive structure as valid parentheses.

What if you needed to generate all combinations for multiple bracket types — (), [], {}?#

Extend the state to track counts per type and add a stack to verify nesting order (e.g., [ must close before the ( that opened after it). The branching factor grows but the pruning principle stays the same.

Could you modify this to use a state-based dynamic programming approach instead of recursion?#

Yes. The state is (opened, closed) and dp[opened][closed] stores all valid string prefixes reachable with exactly that many open and close brackets placed so far.

Build the table bottom-up: start from dp[0][0] = {""}, then for each state extend every prefix by one character — ( if opened < n, ) if closed < opened — and store the results in dp[opened+1][closed] or dp[opened][closed+1].

vector<string> generateParenthesis(int n) {
    // dp[o][c] = all valid prefixes with o opens and c closes placed
    vector<vector<vector<string>>> dp(n + 1, vector<vector<string>>(n + 1));
    dp[0][0] = {""};

    for (int open = 0; open <= n; ++open) {
        for (int close = 0; close <= open; ++close) {
            for (const string& s : dp[open][close]) {
                if (open < n)
                    dp[open + 1][close].push_back(s + '(');
                if (close < open)
                    dp[open][close + 1].push_back(s + ')');
            }
        }
    }
    return dp[n][n];
}

Trade-off vs recursion:

The DP version doesn't save time or space — it trades the call stack for an explicit table of string vectors — but it makes the state machine structure visible, which can be useful when the generation rules are more complex (e.g., weighted or conditional transitions).