Generate Parentheses - Solution & Explanation

Problem Overview: Given n pairs of parentheses, generate every possible string that forms a valid combination. A valid sequence means each opening parenthesis has a matching closing parenthesis and the order never becomes invalid.

Approach 1: Brute Force Generation + Validation (Time: O(2^(2n) * n), Space: O(n))

The naive strategy generates every possible string of length 2n using two characters: ( and ). For each generated string, run a validation check that scans the string and ensures the number of closing parentheses never exceeds openings and the final counts match. This approach explores the entire binary search space of size 2^(2n), most of which are invalid. The validation step takes O(n) time per candidate. While inefficient, it demonstrates the core constraint: the prefix of a valid parentheses string can never contain more ) than (. Useful as a conceptual baseline before applying pruning.

Approach 2: Backtracking with Validity Pruning (Time: O(Cn) ≈ O(4^n / √n), Space: O(n))

The optimized solution builds the string incrementally using backtracking. Instead of generating all possibilities, it only expands states that can still produce a valid result. Track two counters: how many opening parentheses have been used and how many closing parentheses have been placed. You can add ( if the number of openings is less than n. You can add ) only when closing count is less than opening count. These constraints prune invalid branches early, dramatically shrinking the search space.

The recursion continues until the string length reaches 2n, at which point the combination is guaranteed to be valid. The number of valid results equals the Catalan number Cn, which grows approximately as 4^n / √n. Each result requires building a string of length 2n, so the algorithm naturally scales with the number of valid combinations.

This pattern appears frequently in problems that require generating constrained sequences. It combines recursive exploration with strict rules that prevent invalid states from ever forming. The generated strings are typically stored in a list or appended during recursion. Although the result size dominates runtime, the recursion stack itself only requires O(n) space.

Conceptually, the problem sits at the intersection of string construction and recursive search. Some variations use dynamic programming to derive combinations from smaller subproblems, but backtracking remains the most intuitive and interview-friendly implementation.

Recommended for interviews: Backtracking with pruning is the expected solution. Interviewers want to see that you enforce validity during generation rather than filtering afterward. Mentioning the brute force idea first shows understanding of the search space, while implementing the constrained recursion demonstrates algorithmic maturity.