-
Notifications
You must be signed in to change notification settings - Fork 0
054 — Generate Parentheses
LeetCode 22 · Medium. Given n pairs of parentheses, generate all combinations of well-formed (validly nested and balanced) parentheses strings.
Imagine building a string of parentheses one character at a time, and at every step you have (up to) two choices: place an open paren, or place a close paren. Left completely unchecked, this is a full binary decision tree of depth 2n — every possible sequence of ( and ), valid or not. But most branches of that tree are doomed from the start: the moment you've placed more closing parens than opening ones at any point, nothing you add afterward can undo that — the string is dead. A smart builder never even walks down those dead branches. They track two running counts — opens placed, closes placed — and only ever offer a "place close" move when there's an unmatched open still waiting to be closed. That's backtracking: explore, and prune the instant a partial choice can no longer lead anywhere valid.
"Generate all combinations" / "generate all valid parentheses" paired with a validity constraint checked incrementally is the classic DFS-and-Backtracking signal: build a candidate one choice at a time, and abandon a branch the instant it can no longer possibly become valid, rather than building the whole thing and checking at the end. This is not a stack-processing problem in the traditional sense — there's no runtime stack object being pushed and popped to track brackets — but the recursion itself relies on the call stack (see Stacks) to remember "how many opens and closes have I placed so far at this point in the branch," which is exactly the "undo my last choice cheaply" discipline a stack provides.
Generate every possible string of length 2n over the alphabet { (, ) } — a full binary decision tree with no pruning — then filter down to the ones that turn out to be valid, using the same balance-counter check as a validity checker.
func generateParenthesisBruteForce(_ n: Int) -> [String] {
var result: [String] = []
var current: [Character] = []
func isValid(_ chars: [Character]) -> Bool {
var balance = 0
for ch in chars {
balance += (ch == "(") ? 1 : -1
if balance < 0 { return false }
}
return balance == 0
}
func buildAll(_ length: Int) {
if length == 2 * n {
if isValid(current) {
result.append(String(current))
}
return
}
current.append("(")
buildAll(length + 1)
current.removeLast()
current.append(")")
buildAll(length + 1)
current.removeLast()
}
buildAll(0)
return result
}Big-O: O(2^(2n) · n) time — every one of the 2^(2n) length-2n strings over a 2-symbol alphabet gets built, and each is validated in O(n). O(n) space for the recursion depth (excluding the output list, which itself can be exponentially large).
Track openCount and closeCount as the string is built. Only offer ( while openCount < n; only offer ) while closeCount < openCount (there must be an unmatched open waiting). Every branch that's explored is guaranteed to still be extendable into a valid string — invalid branches are never entered at all.
func generateParenthesis(_ n: Int) -> [String] {
var result: [String] = []
var current: [Character] = []
func backtrack(_ openCount: Int, _ closeCount: Int) {
if current.count == 2 * n {
result.append(String(current))
return
}
if openCount < n {
current.append("(")
backtrack(openCount + 1, closeCount)
current.removeLast()
}
if closeCount < openCount {
current.append(")")
backtrack(openCount, closeCount + 1)
current.removeLast()
}
}
backtrack(0, 0)
return result
}
// smoke test
print(generateParenthesis(3))
// ["((()))", "(()())", "(())()", "()(())", "()()()"]
print(generateParenthesis(1))
// ["()"]Big-O: O(4ⁿ / √n) time — bounded by the n-th Catalan number, the exact count of valid sequences, since every recursive call either extends a still-valid partial string or returns immediately. O(n) space for recursion depth and the current string being built (excluding the output).
The brute force explores the entire binary decision tree of depth 2n and only checks validity after a full-length string is already built — most of that tree is wasted work on branches that went invalid many characters ago. The optimal solution moves the validity check earlier: instead of "build everything, then filter," it's "only offer moves that keep the partial string extendable into something valid." Because closeCount < openCount is checked before placing a ), no dead branch is ever entered, so every leaf of the (much smaller) explored tree is already a valid answer — no post-hoc filtering needed at all.
- DFS and Backtracking — the genuine pattern here: build incrementally, prune branches (closing parens) the instant they'd violate validity, exactly the "generate all valid parentheses combinations" example called out in that chapter.
-
Stacks — the recursion's call stack is what makes "undo my last character and try the other branch" (
current.removeLast()) cheap and automatic. - Big-O Notation — for the exponential-but-pruned Catalan-number bound above.
Generate Parentheses is a decision tree with a bouncer at every branch — you're only allowed to place a closing paren if there's still an unmatched open one waiting for it, so every path you're allowed to walk down ends in a valid string.
For n = 2, trace the optimal backtrack function's calls in order, noting (openCount, closeCount) and the string built so far at each step, until it produces the first complete string. Then explain why the guard closeCount < openCount (rather than, say, closeCount < n) is exactly what prevents ever placing a ) with no matching ( before it.
⬅️ Previous: Evaluate Reverse Polish Notation · Next: Daily Temperatures ➡️