Generate Parentheses - Solution & Explanation

Problem Overview: Generate all valid combinations of n pairs of parentheses. A valid sequence means every opening bracket ( is matched with a closing bracket ) in the correct order.

Approach 1: Brute Force Enumeration (O(2^(2n)) time, O(2n) space)

The naive idea generates every possible string of length 2n consisting of ( and ). After generating each candidate, you validate whether it forms a correct parentheses sequence using a counter or stack. Validation takes O(n), and the total candidates are 2^(2n). Most generated strings are invalid, so the algorithm wastes significant work. This approach helps you understand the constraint structure but is not practical for larger n.

Approach 2: Backtracking with Validity Pruning (O(Cn) time, O(n) space)

This is the standard solution used in interviews. Instead of generating all strings, build the sequence incrementally using backtracking. Track two counters: how many opening parentheses and closing parentheses have been used. Add ( if the number of opens is less than n. Add ) only when the number of closes is less than the number of opens. This pruning ensures every partial string remains valid, eliminating invalid branches early. The number of valid results equals the Catalan number Cn, so the time complexity becomes O(Cn), approximately O(4^n / √n), and recursion depth requires O(n) space.

Approach 3: Dynamic Programming using Catalan Construction (O(Cn * n) time, O(Cn) space)

You can also build solutions using dynamic programming. Let dp[i] represent all valid parentheses combinations using i pairs. For each split i, treat one pair as the outer wrapper and combine results from smaller subproblems: ( left ) right, where left comes from dp[j] and right from dp[i-1-j]. This mirrors the Catalan recurrence. The DP approach clearly shows the mathematical structure but requires storing all intermediate results, which increases memory usage compared to recursive generation.

Strings are built character by character, so operations involve simple append and backtrack steps on a mutable buffer or string builder. The recursion tree is heavily pruned because invalid states (more closing than opening parentheses) are never explored. Problems like this commonly appear in string generation and combinatorial search tasks.

Recommended for interviews: Backtracking with pruning. It directly models the constraint that closing brackets cannot exceed opening brackets. Interviewers expect you to recognize the Catalan structure and construct valid sequences incrementally. Mentioning the brute force idea shows you understand the search space, but implementing the pruned backtracking solution demonstrates stronger algorithmic reasoning.