Generate Parentheses: why brute force generates a million failures to find five answers

The problem statement is deceptively simple: given n pairs of parentheses, generate all combinations of well-formed parentheses. For n = 3 that is five strings. For n = 8 it is 1430. The strings themselves are short. The question is how you get to them without wasting time on the roughly (2n)! arrangements that are not valid.

There are two answers. One is naive and correct. The other is naive and correct but three orders of magnitude faster for even modest n. The difference between them is not a clever data structure — it is a shift in when you decide a partial string is going nowhere.

The problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses — strings where every opening bracket has a matching closing bracket in the correct order. Full statement: LeetCode 22.

Constraints:
- 1 <= n <= 8

What n <= 8 forces you to think about

The single constraint is 1 <= n <= 8. That is tiny. The output for n = 8 is 1430 strings of length 16. If you are writing a production utility that generates templates, you run this once and cache the result. Nobody ships n = 10^6 here.

So why does the constraint matter at all? Because it licenses brute force in practice while making the backtracking argument purely educational. The brute-force solution runs in microseconds for n = 8. But (2 * 8)! is 20,922,789,888,000 — over twenty trillion permutations before deduplication. Even if Python generates them at a hundred million per second, you are waiting hours. The constraint allows backtracking to finish in milliseconds. It rules out nothing — you could technically pass with brute force given the deduplication via set() — but the factorial growth is the whole reason the pruned version exists and is worth understanding.

The other thing the constraint tells you: this is a combinatorial enumeration problem, not a search problem. You are not looking for one answer. You are building all of them. That shapes the approach fundamentally.

Approach 1: Brute force — generate everything, keep what works

The most literal reading of the problem: a valid string of length 2n is some arrangement of n opening brackets and n closing brackets. Generate all such arrangements, validate each, collect the valid ones.

from itertools import permutations
from typing import List
 
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        chars = ['('] * n + [')'] * n
        valid = set()
        for perm in permutations(chars):
            candidate = ''.join(perm)
            if self._is_valid(candidate):
                valid.add(candidate)
        return list(valid)
 
    def _is_valid(self, s: str) -> bool:
        balance = 0
        for ch in s:
            if ch == '(':
                balance += 1
            else:
                balance -= 1
                if balance < 0:
                    return False
        return balance == 0

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        char[] chars = new char[2 * n];
        for (int i = 0; i < n; i++) {
            chars[i] = '(';
            chars[i + n] = ')';
        }
        var seen = new HashSet<string>();
        GeneratePermutations(chars, 0, seen);
        return seen.ToList();
    }
 
    private void GeneratePermutations(char[] chars, int start, HashSet<string> seen) {
        if (start == chars.Length) {
            string candidate = new string(chars);
            if (IsValid(candidate)) seen.Add(candidate);
            return;
        }
        for (int i = start; i < chars.Length; i++) {
            Swap(chars, start, i);
            GeneratePermutations(chars, start + 1, seen);
            Swap(chars, start, i);
        }
    }
 
    private void Swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
 
    private bool IsValid(string s) {
        int balance = 0;
        foreach (char c in s) {
            if (c == '(') balance++;
            else {
                balance--;
                if (balance < 0) return false;
            }
        }
        return balance == 0;
    }
}

Complexity. Time: O((2n)! * n) — generating (2n)! permutations and validating each in O(n). Space: O((2n)! * n) for storing all permutations before deduplication. The set deduplication is necessary because permutations(['(','(',')',')']) will produce the same string "(())" multiple times from different swap orderings of the identical characters.

The validation function itself is clean and worth knowing: maintain a balance counter, increment on (, decrement on ), return false immediately if balance ever goes negative, return balance == 0 at the end. This captures both requirements — no premature close, equal counts overall.

Approach 2: Backtracking — build only what can still be valid

The insight is that you do not need to generate a complete string before deciding it is invalid. You can detect invalidity the moment a partial string violates the rules. And the rules for partial strings are simple:

• You can add ( if the number of opening brackets placed so far is less than n.
• You can add ) if the number of closing brackets placed so far is less than the number of opening brackets placed so far.

That second condition is the key. It says: never close a bracket that has not been opened yet. If close < open, adding ) keeps the string potentially valid. If close == open, adding ) would make balance go negative — prune that branch entirely.

from typing import List
 
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
 
        def backtrack(current: str, open_count: int, close_count: int) -> None:
            if len(current) == 2 * n:
                result.append(current)
                return
            if open_count < n:
                backtrack(current + '(', open_count + 1, close_count)
            if close_count < open_count:
                backtrack(current + ')', open_count, close_count + 1)
 
        backtrack('', 0, 0)
        return result

using System.Collections.Generic;
 
public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        var result = new List<string>();
        Backtrack("", 0, 0, n, result);
        return result;
    }
 
    private void Backtrack(string current, int openCount, int closeCount, int n, List<string> result) {
        if (current.Length == 2 * n) {
            result.Add(current);
            return;
        }
        if (openCount < n)
            Backtrack(current + "(", openCount + 1, closeCount, n, result);
        if (closeCount < openCount)
            Backtrack(current + ")", openCount, closeCount + 1, n, result);
    }
}

Complexity. Time: O(4^n / sqrt(n)) — this is the nth Catalan number, which counts exactly the number of valid parenthesis strings. Every call at the base case produces one result; no invalid string is ever fully built. Space: O(4^n / sqrt(n)) for the output, plus O(n) for the call stack (depth at most 2n).

The space breakdown matters here. The call stack is O(n). The output list is O(4^n / sqrt(n) * n) because you store the full string for each valid combination. If someone asks "why not O(n)", the answer is that you have to store the results somewhere.

Hand trace: n = 2 through the decision tree

Walking through by hand, starting from empty string:

• open=0, close=0: only ( is allowed (can't close what hasn't opened). Add (.
• open=1, close=0: can add ( (open < n=2) or ) (close < open=1). Branch both.
  • Left branch adds ( -> ((, open=2, close=0
  • Right branch adds ) -> (), open=1, close=1
• From (( with open=2, close=0: can't add ( (open == n). Must add ). -> ((), open=2, close=1
• From (() with open=2, close=1: can't add (. Add ) -> (()), length 4, emit.
• From () with open=1, close=1: can add ( (open < n=2) or ). But close == open, so can't add ). Add ( -> ()(, open=2, close=1.
• From ()( with open=2, close=1: can't add (. Add ) -> ()(), length 4, emit.

Result: ["(())", "()()"]. Both strings found, zero invalid candidates explored.

Edge cases

n = 1: only one valid string, "()". Backtrack starts with open=0, close=0, adds (, then must add ), hits length 2, emits. One call path, one result. The brute force for n=1 is actually fine: permutations(['(', ')']) gives two arrangements, one valid. The gap only opens at higher n.

n = 8 (maximum): 1430 results. Backtracking explores exactly 1430 leaf nodes. Brute force would need to generate and hash (16)! / (8! * 8!) = 12870 distinct arrangements just from the combinations perspective — but permutations generates 16! total, which is about 2 _ 10^13. That ratio (2 _ 10^13 vs 1430) is what makes backtracking matter even if the constraint is small.

All open first, then all close: ((())) for n=3 — perfectly valid. Backtracking reaches it by always taking the open branch first when available. It is the first leaf in the DFS traversal.

Why no n = 0?: The constraint says 1 <= n. But if you passed n = 0, backtrack starts with len('') == 0 == 2 * 0, immediately emits the empty string, and returns ['']. That is arguably correct for zero pairs.

The pruning invariant, stated precisely

The correctness of backtracking rests on one claim: if at any point close >= open, any completion of the current string is invalid. Proof: you would need to add enough ) to match all (, but you have already added as many ) as (, so any additional ) would exceed the count of (, making balance go negative at some position. The pruning is not just an optimization — it is logically equivalent to the validity check in brute force, just applied early.

Similarly, open > n is always invalid: you cannot use more ( than the total n pairs.

These two pruning conditions together guarantee that every string reaching length 2n in backtracking is valid. No post-validation pass is needed.

Comparison table

For n = 8: brute force visits ~10^13 states; backtracking visits 1430. The O classes do not capture this gap — the concrete numbers do.

What I would ship and why

Backtracking, immediately. Not because of the performance gap — for n <= 8 that gap is academic — but because the code directly encodes the structural rules of valid parentheses. Anyone reading if close_count < open_count understands why that line is there: you can only close a bracket that has already been opened. The brute force version forces a reader to mentally trace permutation generation, deduplication with a set, and a separate validity check. The backtracking version is the problem statement written as code.

The only time I would reach for brute force is if I were prototyping a validator for some other output format and happened to need a known-valid set to test against. In that case, the clarity of "generate all, filter" is appealing precisely because the filtering logic is isolated and testable on its own.

The pattern this problem teaches

Generate Parentheses is the canonical example of constrained enumeration via backtracking. The pattern is:

• You are building a sequence one element at a time.
• At each step, a set of rules determines which elements are valid next choices.
• You apply those rules at construction time, not at validation time.
• Any state that violates the rules is pruned immediately — you never extend it further.

This pattern transfers directly to: letter combinations (LeetCode 17), subsets (LeetCode 78), permutations (LeetCode 46), combination sum (LeetCode 39). The specific pruning condition changes, but the skeleton does not.

The number of valid parenthesis strings for n pairs is the nth Catalan number: C(n) = C(2n, n) / (n + 1). Catalan numbers show up in binary tree enumeration, triangulation of polygons, and stack-sortable permutations — all problems with the same underlying constraint structure. Recognizing that your output count is Catalan-bounded is a sign that backtracking is the right tool.

Where this sits in the stack series

The series has covered Valid Parentheses (20) — checking whether a string is valid — and Evaluate Reverse Polish Notation (150) — using a stack to compute an expression. Generate Parentheses is the constructive counterpart to Valid Parentheses: instead of checking, you are building. That inversion is the conceptual step.

The validity logic from problem 20 appears here as the pruning condition. You already know balance >= 0 at all prefixes and balance == 0 at the end are the two requirements. Here you enforce them during construction instead of after.

Letter Combinations of a Phone Number (17) has the same backtracking skeleton. The constraint is not balance of open/close but the mapping from digit to letter set. The depth is fixed (one character per digit), and at each level you branch over the letter set. Same structure, different branching condition.

Remove Invalid Parentheses (301) inverts the direction: given a string that may be invalid, find all ways to remove the minimum number of characters to make it valid. Now you are searching a space of deletions rather than building from scratch. The validity check is the same; the search direction is reversed.

Different Ways to Add Parentheses (241) asks how many ways you can parenthesize an arithmetic expression. The answer involves the Catalan number in a different form — you are counting parse trees rather than strings, but the combinatorial structure is identical.