22. Generate Parentheses
Asked at Google, Oracle, Salesforce, Walmart and 1 more
Difficulty
Medium
Time
O(4^n / sqrt(n))
Space
O(n)
Pattern
String
Companies
5
Problem
You are given an integer n, the number of pairs of parentheses you must use. Return all strings of length 2n that are well-formed. A string is well-formed when every ( has a matching ) after it, and no prefix ever has more ) than (.
Each result must use exactly n opening brackets and n closing brackets. The order of the strings in your answer does not matter.
The classic way to solve this is backtracking: build the string one character at a time. At each step you may add ( if you have not used all n of them yet, or add ) if the number of closing brackets so far is still smaller than the number of opening brackets. When the string reaches length 2n, it is complete and valid, so you save it.
Build valid strings only
Constraints
- ●
1 <= n <= 8
Examples
n = 3["((()))","(()())","(())()","()(())","()()()"]n = 1["()"]Asked At
5 companies| 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 → |
| Bloomberg | Medium | View all Bloomberg 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.
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.
Backtracking tree for n = 2
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
O(4^n / sqrt(n)) timedef 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 runs in O(4^n / sqrt(n)) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Generate Parentheses?
Generate Parentheses is asked at Google, Oracle, Salesforce, Walmart, Bloomberg. 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.