Generate Parentheses
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 3
- Core for
- 9 roles
The problem
Given a positive integer n representing the number of pairs of parentheses, generate all combinations of well-formed parentheses. A well-formed string has every opening bracket matched by a closing bracket in the correct order.
Example 1
- Input
- n = 3
- Output
- ["((()))","(()())","(())()","()(())","()()()"]
- Why
- All 5 valid combinations of 3 pairs of parentheses are generated.
Example 2
- Input
- n = 1
- Output
- ["()"]
- Why
- With a single pair, the only valid combination is ().
Constraints
- 1 <= n <= 8
- The output contains only well-formed parentheses strings
How to think about it
Updated 2026-09-29A valid prefix never contains more closing parentheses than opening ones, and neither bracket can ever appear more than n times total. Instead of generating arbitrary sequences and filtering, track the count of placed open and close brackets; place an open bracket whenever count is under n, and a close bracket whenever close is strictly less than open.
Approaches, worst first
Generate all 2^(2n) sequences and validate
time O(2^(2n) * n) · space O(n)
Recursively append either '(' or ')' at every of the 2n positions. When a string reaches length 2n, run a stack-based balance validator. Loses because the vast majority of generated candidates violate parenthesis balance within the first few characters.
Backtracking with balance invariantsWrite this one
time O(4^n / sqrt(n)) · space O(n)
Build candidates character by character. Only branch into '(' if open count < n, and into ')' if close count < open count. Every branch is guaranteed to stay valid, visiting exactly the Catalan number C_n valid paths without wasted leaves.
Where people lose marks · 2
- Permitting close count to advance when `close == open` introduces an unmatchable closing bracket that can never be repaired by subsequent characters.
- Modifying a shared string or buffer in place without popping or slicing during backtrack causes characters from dead branches to leak into subsequent recursive calls.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .