Generate Parentheses
Last Updated: April 1, 2026
Understanding the Problem
We need to produce every possible string of length 2n made up of ( and ) characters that forms valid (balanced) parentheses. "Valid" means every opening parenthesis has a corresponding closing one, and at no point while reading left to right do we encounter more closing brackets than opening ones.
What makes this different from simply generating all permutations of n opening and n closing brackets? Most of those permutations would be invalid. For instance, )( uses one of each but is not well-formed. The challenge is to enumerate only the valid strings efficiently, without generating and filtering all 2^(2n) possibilities.
The key observation is that we can build these strings character by character. At each position, we decide whether to place ( or ). As long as we track how many opening and closing brackets we have used so far, we can enforce validity as we go: we can place ( if we have not used all n of them, and we can place ) only if the count of closing brackets used is less than the count of opening brackets used. This naturally leads to a backtracking solution.
Key Constraints:
1 <= n <= 8→ The maximum input is tiny. With n = 8, there are only 1,430 valid combinations (the 8th Catalan number). Even brute-force enumeration of all 2^16 = 65,536 binary strings would be fast.- Output size grows as the Catalan number C(n) = C(2n, n) / (n+1). For n = 8, C(8) = 1,430. This is small enough that any reasonable generation method will work.
Approach 1: Brute Force (Generate All and Filter)
Intuition
The most straightforward approach is to generate every possible string of length 2n using the characters ( and ), then keep only the ones that are valid. Each position in the string has two choices, so there are 2^(2n) total strings. We check each one by scanning left to right and tracking the balance (increment for (, decrement for )). If the balance never goes negative and ends at zero, the string is valid.
This is conceptually simple but wasteful. For n = 8, we generate 65,536 strings but only 1,430 are valid. That is about 2% efficiency. Still, with n capped at 8, it runs fast enough.
Algorithm
- Generate all 2^(2n) binary strings of length 2n, where 0 maps to
(and 1 maps to). - For each string, check if it is valid: scan left to right, keeping a running balance. Add 1 for
(, subtract 1 for). If balance goes negative at any point, the string is invalid. If balance is zero at the end, it is valid. - Collect all valid strings into the result.
Example Walkthrough
Code
- Time Complexity: O(2^(2n) * n). We generate 2^(2n) strings, and for each one we scan its entire length (2n) to check validity.
- Space Complexity: O(n). The recursion stack goes 2n levels deep, and we use a character array of size 2n. Output space is not counted.
We generate every possible string including the vast majority that are invalid. What if we could check validity as we build the string and stop going down a path the moment it becomes impossible to form a valid result?
Approach 2: Backtracking with Open/Close Counts
Intuition
Instead of generating everything and filtering, we build the string one character at a time and make smart choices at each step. The key insight is that we only need two counters: open (how many ( we have placed) and close (how many ) we have placed). At any point during construction:
- We can place
(ifopen < n(we still have opening brackets left to use). - We can place
)ifclose < open(we have unmatched opening brackets that need closing).
These two simple rules guarantee that every string we complete is valid. We never explore a dead-end path because we never place a character that would make the string invalid. This is classic backtracking: make a choice, recurse, then undo the choice and try the next option.
The beauty of this approach is that it generates exactly the Catalan number C(n) of valid strings, with no wasted work on invalid ones.
The two rules (open < n and close < open) are both necessary and sufficient for validity. The first ensures we do not use more than n opening brackets. The second ensures we never have more closing brackets than opening ones at any prefix, which is exactly the definition of a balanced parentheses prefix. Since we only add to the result when the string reaches length 2n, and at that point open == close == n is guaranteed by the branching logic, every result string is valid.
This is a textbook example of how backtracking can eliminate invalid states early, turning an exponential search space into one that only visits valid states.
Algorithm
- Start with an empty string and both
openandclosecounters at 0. - If the string length equals 2n, we have a complete valid combination. Add it to the result.
- If
open < n, append(and recurse withopen + 1. - If
close < open, append)and recurse withclose + 1. - Backtrack by removing the last character after each recursive call.
Example Walkthrough
Code
- Time Complexity: O(4^n / sqrt(n)). The number of valid parentheses strings is the nth Catalan number. Each string has length 2n, so total work is O(n * C(n)).
- Space Complexity: O(n). The recursion stack goes at most 2n levels deep. The current string being built takes O(n) space. Output space is not counted.
This approach is already optimal for generating all valid strings. But there is an alternative that reveals a beautiful mathematical structure: every valid string can be decomposed as ( + inner + ) + outer, based on where the first ( finds its matching ).
Approach 3: Divide and Conquer (Closure Number)
Intuition
There is an elegant mathematical structure behind valid parentheses. Consider any valid string with n pairs. The first character must be (. Somewhere later in the string, there is a ) that matches this first (. Let's say the matching ) is at index 2k + 1 (0-indexed). Then the string looks like:
( + [valid string with k pairs] + ) + [valid string with n-1-k pairs]
The part inside the first matched pair is a valid string of k pairs (for k from 0 to n-1), and the part after is a valid string of the remaining n-1-k pairs. This is called the "closure number" decomposition.
By iterating k from 0 to n-1 and recursively generating the strings for k pairs and n-1-k pairs, we can build all valid strings for n pairs. This is essentially the recursive definition of the Catalan numbers in action.
Every valid parentheses string has a unique decomposition based on where the first ( finds its matching ). If the matching ) is at position 2k+1, there are exactly k pairs inside and n-1-k pairs outside. By iterating over all possible values of k, we cover every possible structure. The recursive calls generate all valid strings for the sub-problems, and the nested loops combine them in all possible ways.
This directly mirrors the Catalan number recurrence: C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)*C(0). Each term corresponds to one value of k, and the product of Catalan numbers counts the combinations of inner and outer strings.
Algorithm
- Base case: for n = 0, return a list containing just the empty string
"". - For each value of k from 0 to n-1:
a. Recursively generate all valid strings of k pairs (these go inside the first matched pair).
b. Recursively generate all valid strings of n-1-k pairs (these go after the first matched pair).
c. For each combination of inner and outer strings, create "(" + inner + ")" + outer and add it to the result.
- Return all generated strings.
Example Walkthrough
Code
- Time Complexity: O(4^n / sqrt(n)). Same as Approach 2. We generate exactly C(n) strings, each of length 2n.
- Space Complexity: O(4^n / sqrt(n)). Unlike the backtracking approach, this builds and stores all sub-problem results in memory before combining them.