Generate Parentheses
Given $n$ pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Why Interviewers Ask This
Google asks this question to evaluate a candidate's mastery of recursion, backtracking, and state management. It tests the ability to prune invalid search spaces efficiently rather than generating all permutations blindly. Interviewers specifically look for logical clarity in maintaining balance constraints while constructing valid sequences dynamically.
How to Answer This Question
1. Clarify Requirements: Confirm input n is positive and define 'well-formed' as every opening bracket having a matching closing bracket in correct order. 2. Define State Variables: Identify that you need to track the count of open brackets used and closed brackets placed so far. 3. Establish Base Case: Determine when to stop recursion, which occurs when the current string length equals 2*n. 4. Formulate Recursive Logic: Explain that you can add an open parenthesis if open_count < n, and a closing parenthesis only if closed_count < open_count. 5. Pruning Strategy: Emphasize how these conditions naturally prevent invalid combinations without needing post-generation validation. 6. Complexity Analysis: Discuss time complexity O(4^n / sqrt(n)) based on Catalan numbers and space complexity O(n) for the recursion stack depth.
Key Points to Cover
- Explicitly defining the pruning condition (close_count < open_count) to avoid invalid states
- Demonstrating understanding of Catalan numbers regarding the output size
- Clearly articulating the base case where string length equals 2*n
- Explaining why brute force generation followed by filtering is inefficient
- Maintaining clean variable naming and logical flow in the explanation
Sample Answer
To solve the Generate Parentheses problem efficiently, I would use a backtracking approach with pruning. First, I'd clarify that we need exactly n pairs where every opening bracket has a corresponding closing one. My solution will maintain two counters: open_count and close_count, representing the number of left and right parentheses currently in our path.
The core logic relies on two simple rules during recursion. We can append an open parenthesis '(' whenever open_count is less than n. Crucially, we can only append a closing parenthesis ')' if close_count is strictly less than open_count. This second rule is vital because it ensures we never close more brackets than we have opened, effectively pruning the entire search tree of invalid combinations immediately.
For example, if n is 3, we start with an empty string. We add '(', then another '(', then another '('. Once we hit three opens, we cannot add more. Now, since we have three opens and zero closes, we must add closes until they match. If at any point we tried to add a close bracket before an open, the condition close_count < open_count would fail, and that branch dies instantly.
This approach avoids generating the factorial number of total permutations (2n choose n) and focuses only on valid Catalan structures. The time complexity is proportional to the number of valid outputs, which is the nth Catalan number, making it highly efficient for Google's scale expectations. Space complexity is O(n) for the recursion stack.
Common Mistakes to Avoid
- Attempting to generate all 2^(2n) permutations first and then filtering them out, which is computationally wasteful
- Failing to pass the current counts or string by reference/value correctly, leading to shared state bugs
- Not handling edge cases like n=0 or negative inputs before starting the recursion
- Confusing the condition for adding a closing bracket, such as checking against n instead of open_count
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.