Cracking The Coding Interview Together – Problem 8.9: Parenthesis

Have you ever stared at a recursive function, wondering if it's generating redundant states or exploding your call stack? We've all been there. When building combinatorial generators, the difference between an elegant O(4^n / sqrt(n)) solution and a brute-force nightmare often boils down to a single invariant: pruning invalid paths before we even step down them. Today, we are tackling Problem 8.9 from Cracking the Coding Interview: Parens. Our shared goal is to understand how to construct these combinations efficiently by maintaining strict state invariants, transforming a complex generation problem into a predictable, bounded traversal.

Problem Statement

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n pairs of parentheses. For example, given n = 3, your solution should return or print the following combinations:

((())), (()()), (())(), ()(()), ()()()

Our operational goals are straightforward: we need to generate every unique valid combination without duplicates, ensure optimal time complexity by avoiding dead ends, and structure our code so it remains maintainable and easy to reason about.

Analyze the Problem Together

Let's break down the constraints and find the "Aha!" conflict. If we try to approach this problem naively—say, by generating all permutations of n left parentheses and n right parentheses and then validating each one—we would examine (2n)! / (n! * n!) combinations. For n = 3, that's 20 combinations. For n = 10, that number balloons into millions of wasted checks.

The "Aha!" moment comes when we realize we don't need a validator function at all. Instead of generating and checking, we can construct the string character by character, tracking the count of open and closed parentheses we have used so far. By enforcing two simple rules at every single step, we completely eliminate invalid paths:

• Rule 1: We can add a left parenthesis as long as we haven't used up all n left parentheses (i.e., leftCount < n).
• Rule 2: We can add a right parenthesis as long as the number of right parentheses is strictly less than the number of left parentheses (i.e., rightCount < leftCount).

This state-space tree guarantees that every leaf node we reach is a 100% valid parenthesis combination.

Questions for the Interviewer

Before writing a single line of production code, a senior engineer always clarifies expectations:

• Should the output be returned as a List<String>, or printed directly to standard output? (Usually, returning a list is preferred for testability).
• Can we assume n is a non-negative integer, and what is the expected upper bound for n?
• Are there memory constraints we should worry about regarding the size of the resulting collection?

Think About the Solution

We will use a backtracking approach (a specialized form of depth-first search) implemented via recursion. Our recursive function will accept:

• A List<String> results accumulator.
• A character array (or StringBuilder) representing the current string being built.
• An integer leftCount tracking how many ( characters we have placed.
• An integer rightCount tracking how many ) characters we have placed.
• An integer n representing the target pair count.

When both leftCount and rightCount equal n, our character array is full, and we add its string representation to our results list.

Write Code And Explain

Here is the production-ready Java implementation:

import java.util.ArrayList;
import java.util.List;

public class ParenthesesGenerator {

    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        // The total length of each string will be 2 * n
        char[] current = new char[2 * n];
        backtrack(result, current, 0, 0, n);
        return result;
    }

    private static void backtrack(List<String> result, char[] current, int leftCount, int rightCount, int n) {
        // Base case: when we have used all left and right parentheses
        if (leftCount == n && rightCount == n) {
            result.add(new String(current));
            return;
        }

        // Try adding a left parenthesis if we haven't reached the limit
        if (leftCount < n) {
            current[leftCount + rightCount] = '(';
            backtrack(result, current, leftCount + 1, rightCount, n);
        }

        // Try adding a right parenthesis if it won't exceed the left count
        if (rightCount < leftCount) {
            current[leftCount + rightCount] = ')';
            backtrack(result, current, leftCount, rightCount + 1, n);
        }
    }
}

Step-by-Step Walkthrough:

1. We initialize a pre-sized character array of length 2 * n. This avoids string concatenation overhead and keeps memory allocations minimal.
2. We invoke backtrack with zeroed counts.
3. At each frame, we check if we can safely branch left (add () or branch right (add )). Notice how we index into current using leftCount + rightCount, which represents our current depth in the decision tree.
4. Once leftCount == n and rightCount == n, we materialize a new String from the char array and store it in our results list.

Time & Space Complexity

Let's analyze the performance profile of our backtracking algorithm:

• Time Complexity: $\mathcal{O}(\frac{4^n}{\sqrt{n}})$. The total number of valid parenthesis combinations for n pairs is given by the $n$-th Catalan number. While the worst-case exploration is bounded by this Catalan number growth rate, we perform zero invalid explorations.
• Space Complexity: $\mathcal{O}(n)$ auxiliary stack space for the recursion tree depth, plus $\mathcal{O}(n)$ for the character array buffer. (Note: Output storage space is excluded from auxiliary complexity, as storing all valid strings requires $\mathcal{O}(n \cdot C_n)$ space).

Why This Problem Matters (The Senior Perspective)

Combinatorial generation problems like Parens appear everywhere in systems engineering from generating abstract syntax tree (AST) permutations in compilers to testing routing expressions in API gateways. Understanding how to prune a search space dynamically rather than filtering a posteriori is a hallmark of senior engineering. When dealing with large state spaces in distributed systems or concurrent job schedulers, applying these exact bounding techniques prevents CPU exhaustion and memory leaks.

Final Thoughts

We've successfully solved Problem 8.9 by leveraging state-space pruning and efficient buffer management. Take some time to experiment with this code—try rewriting it iteratively or modifying it to handle multiple types of brackets like {} and []. Keep practicing, keep building, and happy coding!