Generate Parentheses
Asked at Google, Oracle, Salesforce, Walmart
Problem
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For n = 3, there are 5 distinct combinations.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Oracle | Medium | View all Oracle questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Backtracking: build strings character by character. At each position, you can add "(" if you haven't used all n open brackets, or ")" if adding it won't make the string invalid (close count < open count).
Validity constraint: at any point in the construction, the number of closing parentheses must never exceed the number of opening parentheses. This ensures every prefix of the result is valid.
The two rules: (1) add "(" if openCount < n, (2) add ")" if closeCount < openCount. When the string length reaches 2n, you have a complete valid combination.
Visual walkthrough for n=2:
Start: "", open=0, close=0
"(": open=1, close=0
"((": open=2, close=0
"(()": open=2, close=1
"(())": open=2, close=2. Length=4. Add to result.
"()": open=1, close=1
"()(" : open=2, close=1
"()()": open=2, close=2. Length=4. Add to result.
Result: ["(())", "()()"].
Edge cases: n=1 (return ["()"]), n=0 (return [""]).
Optimal Approach
Step 1: Define backtrack function with current string, open count, close count.
Step 2: Base case: if string length == 2n, add to result.
Step 3: If openCount < n, add "(" and recurse.
Step 4: If closeCount < openCount, add ")" and recurse.
Step 5: Return all generated combinations.
The backtracking naturally prunes invalid branches. You never generate a string with more closing than opening brackets.
Time: O(4^n / sqrt(n)) (Catalan number). Space: O(n) recursion depth.
What Trips People Up in Real Interviews
Not pruning invalid branches early. The key insight is that you only add ")" when closeCount < openCount. Skipping this check generates invalid combinations like "())" and wastes time exploring dead ends.
Confusing openCount and closeCount roles. openCount tracks how many "(" have been placed (max n), closeCount tracks ")" (max openCount). Swapping these conditions produces strings that are never valid.
Using a set to deduplicate results. Backtracking with the two rules naturally produces unique combinations without duplicates. A set is unnecessary overhead and signals a misunderstanding of the algorithm.
Building the string incorrectly by concatenating inside the recursion without backtracking. In Python, strings are immutable, so s + "(" creates a new string each call. This is fine. But if using a mutable list, you must undo the last character after recursion returns.
Forgetting the base case length check. The recursion stops when len(s) == 2 * n. Without this check, the function recurses infinitely or produces incomplete strings. Some candidates use openCount == n && closeCount == n which is equivalent but less clear.
Solution Code
def generateParenthesis(n):
result = []
def backtrack(s, open_count, close_count):
if len(s) == 2 * n:
result.append(s)
return
if open_count < n:
backtrack(s + '(', open_count + 1, close_count)
if close_count < open_count:
backtrack(s + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return resultFrequently Asked Questions
What is the Generate Parentheses problem?
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For n = 3, there are 5 distinct combinations.
How do you solve Generate Parentheses?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Generate Parentheses?
Generate Parentheses is asked at Google, Oracle, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on Generate Parentheses?
- Not pruning invalid branches early. The key insight is that you only add ")" when `closeCount < openCount`. Skipping this check generates invalid combinations like "())" and wastes time exploring dead ends.
- Confusing `openCount` and `closeCount` roles. `openCount` tracks how many "(" have been placed (max n), `closeCount` tracks ")" (max openCount). Swapping these conditions produces strings that are never valid.
- Using a `set` to deduplicate results. Backtracking with the two rules naturally produces unique combinations without duplicates. A `set` is unnecessary overhead and signals a misunderstanding of the algorithm.
- Building the string incorrectly by concatenating inside the recursion without backtracking. In Python, strings are immutable, so `s + "("` creates a new string each call. This is fine. But if using a mutable list, you must undo the last character after recursion returns.
- Forgetting the base case length check. The recursion stops when `len(s) == 2 * n`. Without this check, the function recurses infinitely or produces incomplete strings. Some candidates use `openCount == n && closeCount == n` which is equivalent but less clear.