March 24
Generate Parentheses
How to use counter-based backtracking to prune invalid prefixes before they turn into wasted work.
Backtracking Intermediate 20 min TypeScript
Given an integer n, return all combinations of n pairs of well-formed parentheses.
In the SeniorPath playground, return the combinations in the natural DFS order that tries ( before ) to keep comparison deterministic.
Example:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
What to notice before coding
- The problem does not ask for any string with `(` and `)`. It asks only for well-formed ones.
- Prefixes matter. If a prefix is already invalid, no suffix can save it.
- The needed state fits in two counters and the current string.
Common mistakes
- generating all strings of length `2n` and validating only at the end
- allowing more closing parentheses than opening ones in some prefix
Step 1 - Understand what makes a combination valid
It is not enough to have n openings and n closings.
Order matters.
Example:
"()()"is valid")(()"is not
The reason is that, reading from left to right, a closing parenthesis can never appear before there is an opening one to match it.
Step 2 - Write the most direct baseline
The natural baseline is:
- generate all strings of length
2 * n - filter only the valid ones at the end
It works.
But it wastes a lot of work on strings that were doomed from the start.
Step 3 - Ask what you can know early
During string construction, two rules are always true:
- you can only open if there are openings left
- you can only close if there is some unmatched opening
That means you can prune long before the end.
Step 4 - Turn the rule into backtracking
The needed state is small:
- how many
(you used - how many
)you used - the current string
The decision at each step becomes:
- do I try opening?
- do I try closing?
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function generateParenthesis(n: number): string[] {
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(number of valid combinations * n)
Space: O(n)
Solution 1 - Generate everything and validate later
Good baseline because it makes the waste obvious.
function isValid(candidate: string): boolean {
let balance = 0
for (const char of candidate) {
balance += char === "(" ? 1 : -1
if (balance < 0) {
return false
}
}
return balance === 0
}
export function generateParenthesis(n: number): string[] {
const result: string[] = []
function dfs(current: string): void {
if (current.length === n * 2) {
if (isValid(current)) {
result.push(current)
}
return
}
dfs(`${current}(`)
dfs(`${current})`)
}
dfs("")
return result
}It works, but it generates many strings that never had any chance.
Solution 2 - Backtracking with counter-based pruning
Now you avoid building invalid prefixes.
export function generateParenthesis(n: number): string[] {
const result: string[] = []
function dfs(current: string, openUsed: number, closeUsed: number): void {
if (current.length === n * 2) {
result.push(current)
return
}
if (openUsed < n) {
dfs(`${current}(`, openUsed + 1, closeUsed)
}
if (closeUsed < openUsed) {
dfs(`${current})`, openUsed, closeUsed + 1)
}
}
dfs("", 0, 0)
return result
}The strong insight is that good backtracking does not try everything. It only tries what can still work.
What to say in the interview
A strong short explanation would be:
The baseline generates all strings of length
2nand validates later, but that wastes work. The stronger version usesbacktrackingwith two counters. I only open if there are openings left, and I only close ifclose < open. That lets me prune invalid prefixes early and generate only viable combinations.
That shows that you:
- understand the difference between generate and prune
- can explain the validity rule clearly
- turn the constraint into a local decision
When this pattern shows up again
This pattern comes back when you need to:
- build the answer step by step
- prune invalid prefixes early
- use
backtrackingwith simple constraints - think in counters and local state
The point is not memorizing
Generate Parentheses.
The point is learning to cut bad search early.