22. Generate Parentheses

This problem trips up many candidates because it looks like a simple string generation task, but actually requires a structured way to explore only valid sequences without wasting effort on invalid ones. The core lesson here is learning how the subsets/backtracking pattern lets you build combinations incrementally, making decisions at each step about whether to include an opening or closing parenthesis. Once you see that every partial sequence must maintain a balance invariant (never more closing than opening parentheses), the recursive structure clicks into place and becomes a powerful template for many similar generation problems.

Problem statement

Given a positive integer n, generate all possible strings that represent valid (well-formed) combinations of n pairs of parentheses.

A string of parentheses is considered valid if every opening parenthesis ( has a corresponding closing parenthesis ) that appears after it, and at no point while reading the string from left to right does the number of closing parentheses exceed the number of opening parentheses.

Return the list of all such valid strings in any order.

Constraints

• 1 ≤ n ≤ 8
• Each output string has a length 2 * n
• The number of valid combinations is the nth Catalan number

Examples

Why enumerating all possibilities doesn’t scale

A naive approach would generate every possible string of length 2n using the characters ( and ), then filter out the invalid ones. This means producing 2^(2n) candidate strings. For n = 8, that is over 65,000 strings, the vast majority of which are invalid. Even worse, checking validity for each candidate requires a linear scan, compounding the wasted work.

The fundamental issue is that this brute enumeration treats every position independently, ignoring the structural constraints that link earlier characters to later ones. Most generated strings violate validity long before they are complete, meaning work was spent building prefixes that could never lead to a correct answer. What we need instead is a method that only ever constructs strings that remain valid at every step, pruning entire branches of the search space the moment a constraint would be violated.

Optimized approach

The subsets pattern with backtracking fits this problem perfectly. Instead of generating all strings and filtering, we build each string character by character, making a binary choice at each position: append ( or append ). Two simple rules govern these choices:

1. We can append ( only if the count of opening parentheses used so far is less than n.
2. We can append ) only if the count of closing parentheses used so far is strictly less than the count of opening parentheses.

These two rules guarantee that every string we construct is valid by the time it reaches length 2n. The recursion naturally explores all valid branches, and backtracking (removing the last character after exploring a branch) ensures we reuse a single working list rather than creating new strings at every recursive call.

This is essentially the subsets pattern applied to a constrained decision tree: at each level of the tree, we choose from a set of valid options, recurse deeper, and then undo our choice to explore alternatives.

Why the optimized approach works well

The two placement rules act as aggressive pruning conditions. At every node in the recursion tree, at least one option is eliminated whenever the counts reach their limits. This means the algorithm only visits nodes that correspond to prefixes of valid strings, and the total number of complete strings it produces is exactly the nth Catalan number, C(n), which grows much more slowly than 2^(2n).

Because each recursive call either adds a character or hits a base case, the depth of recursion is exactly 2n, which is small for the given constraints. The backtracking approach also keeps memory usage minimal by mutating a single list in place rather than copying strings at every level.

Step-by-step algorithm

1. Initialize an empty list result to collect all valid combinations and an empty list output to build the current combination character by character.
2. Define a recursive function back_track that accepts the target number of pairs n, the current count of left parentheses left_count, the current count of right parentheses right_count, the working list output, and the collection list result.
3. If both left_count and right_count equal n, join the characters in output into a string and append it to result. This is the base case where a complete valid combination has been formed.
4. If left_count is less than n, append ( to output, recursively call back_track with left_count + 1, and after returning, remove the last character from output to backtrack.
5. If right_count is less than left_count, append ) to output, recursively call back_track with right_count + 1, and after returning, remove the last character from output to backtrack.
6. Start the process by calling back_track with left_count = 0 and right_count = 0.
7. Return result.

Python implementation

def back_track(n, left_count, right_count, output, result):
    # Base case: both counts have reached n, so the combination is complete
    if left_count >= n and right_count >= n:
        result.append("".join(output))
        return

    # Option 1: add an opening parenthesis if we haven't used all n
    if left_count < n:
        output.append('(')
        back_track(n, left_count + 1, right_count, output, result)
        output.pop()  # backtrack by removing the last character

    # Option 2: add a closing parenthesis if it won't break validity
    if right_count < left_count:
        output.append(')')
        back_track(n, left_count, right_count + 1, output, result)
        output.pop()  # backtrack by removing the last character


def generate_combinations(n):
    result = []
    output = []
    back_track(n, 0, 0, output, result)
    return result


# Driver code
def main():
    test_cases = [1, 2, 3, 4, 5]

    for i, n in enumerate(test_cases):
        print(f"{i + 1}.\tn = {n}")
        result = generate_combinations(n)
        print(f"\tNumber of valid combinations: {len(result)}")
        for combo in result:
            print(f"\t\t{combo}")
        print("-" * 100)


if __name__ == '__main__':
    main()

Time complexity

The time complexity is O(4^n / sqrt(n)). This comes from the fact that the number of valid parentheses combinations for n pairs is the nth Catalan number, C(n) = (2n)! / ((n+1)! * n!), which is asymptotically bounded by 4^n / (n^(3/2) * sqrt(pi)). For each valid combination, constructing the string of length 2n takes O(n) time. Therefore, the total work is O(n * C(n)), which simplifies to O(4^n / sqrt(n)). Within the given constraint of n ≤ 8, this is extremely fast.

Space complexity

The space complexity is O(n) for the recursion stack and the working output list, since the maximum depth of recursion is 2n and the output list holds at most 2n characters at any time. The result list itself holds all C(n) strings of length 2n, which requires O(n * C(n)) space, but this is considered output space rather than auxiliary space. If we exclude the output, the auxiliary space is O(n).

Edge cases

• n = 1: The only valid combination is "()". The algorithm correctly produces a single result after one open and one close placement.
• n = 8 (upper bound): Produces 1430 valid strings, each of length 16. The algorithm handles this comfortably within the constraints, demonstrating that the pruning keeps the search space manageable.
• All nesting vs all sequential: For any n, the algorithm generates both the fully nested form like "(((...)))" and the fully sequential form like "()()...())", along with every valid mixture in between.

Common pitfalls

• Forgetting to backtrack: After a recursive call, candidates sometimes forget to pop the last character from the working list. This corrupts the state for sibling branches and produces incorrect or incomplete results.
• Using string concatenation instead of a list: Building strings with + at every recursive call creates a new string object each time, leading to O(n) overhead per call. Using a mutable list and joining only at the base case is more efficient.
• Incorrect closing parenthesis condition: A common mistake is checking right_count < n instead of right_count < left_count. The former allows invalid sequences where ) appears before a matching (.
• Not recognizing the subsets pattern: Some candidates try dynamic programming or iterative approaches that are harder to implement correctly. Recognizing this as a constrained subset generation problem makes the backtracking solution straightforward to write and reason about.