Generate Parentheses
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.
This differs from arranging n opening and n closing brackets in every possible order, because most of those arrangements are invalid. For example, )( uses one of each but is not well-formed. The challenge is to enumerate only the valid strings without generating and filtering all 2^(2n) possibilities.
One option is to build the strings character by character. At each position, we choose ( or ). If we track how many opening and closing brackets we have placed so far, we can enforce validity during construction: place ( while fewer than n of them have been used, and place ) only while the count of closing brackets is less than the count of opening brackets. That rule leads to a backtracking solution.
Key Constraints:
1 <= n <= 8keeps the input small. At n = 8 there are 1,430 valid combinations (the 8th Catalan number), and even enumerating all 2^16 = 65,536 binary strings finishes in well under a second. The small bound makes a brute-force approach viable, though better ones exist.- The output size is the Catalan number C(n) = C(2n, n) / (n+1). For n = 8, C(8) = 1,430. Any generation method that produces only valid strings does work proportional to this count, so the output itself dominates the running time.
Approach 1: Brute Force (Generate All and Filter)
Intuition
Generate every string of length 2n over the characters ( and ), then keep the valid ones. Each position has two choices, so there are 2^(2n) total strings. Validity is checked by scanning left to right and tracking a running balance: increment for (, decrement for ). The string is valid when the balance never goes negative and ends at zero.
This wastes most of its work. For n = 8 it builds 65,536 strings but only 1,430 are valid, so roughly 98% of the strings are discarded. With n capped at 8 it still finishes quickly.
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.
The waste comes from completing strings whose prefix is already invalid. The next approach checks validity during construction and abandons any prefix that can no longer become balanced.
Approach 2: Backtracking with Open/Close Counts
Intuition
Build the string one character at a time, but only ever place a character that keeps the prefix extendable to a valid string. Two counters carry all the state we need: open (how many ( we have placed) and close (how many ) we have placed). At each step:
- Place
(ifopen < n, since opening brackets remain to be used. - Place
)ifclose < open, since there is an unmatched(waiting to be closed.
Every string that reaches length 2n under these rules is valid, so no time is spent on dead ends. This is backtracking: make a choice, recurse, undo the choice, try the next option. The number of strings produced is exactly the Catalan number C(n).
The condition close < open is what guarantees validity. A prefix is a valid parentheses prefix if at no point does the closing count exceed the opening count. The rule allows ) only when close < open, so after placing it close <= open still holds, meaning the running balance never drops below zero. The condition open < n caps the opening brackets at n. When the string reaches length 2n, we have placed 2n characters with at most n of each, which forces exactly n of each, so open == close == n and the balance ends at zero. A prefix-balanced string that ends at balance zero is valid.
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 is already optimal in the sense that it produces only valid strings. A different approach builds them from a recursive structure instead: every valid string splits as ( + inner + ) + outer at the position where the first ( meets its matching ).
Approach 3: Divide and Conquer (Closure Number)
Intuition
Valid parentheses have a recursive structure that maps directly onto the Catalan recurrence. Take any valid string with n pairs. Its first character is (, and somewhere later sits the ) that matches it. Say that matching ) is at index 2k + 1 (0-indexed). Everything between them is a valid string of k pairs, and everything after it is a valid string of n-1-k pairs:
( + [valid string with k pairs] + ) + [valid string with n-1-k pairs]
The value k is the "closure number" of the first pair. Iterating k from 0 to n-1 and recursively generating all strings of k pairs and all strings of n-1-k pairs builds every valid string of n pairs.
The decomposition is unique because the matching ) for the first ( is determined by the string: it is the first position where the running balance returns to zero. So every valid string corresponds to exactly one value of k, with k pairs strictly inside the first pair and n-1-k pairs strictly after it. Conversely, gluing any valid k-pair string inside and any valid (n-1-k)-pair string after a fresh pair yields a valid string. Iterating k from 0 to n-1 and combining every inner with every outer therefore produces each valid string once. This is the Catalan recurrence C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)*C(0): each term is one value of k, and the product counts the inner-outer combinations.
Algorithm
- Base case: for n = 0, return a list containing only the empty string
"". - For each value of k from 0 to n-1:
- Recursively generate all valid strings of k pairs (these go inside the first matched pair).
- Recursively generate all valid strings of n-1-k pairs (these go after the first matched pair).
- For each combination of inner and outer strings, create
"(" + inner + ")" + outerand 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.