Well-Nested Bracket Strings
MediumBacktracking
Problem
A template engine needs every way to arrange n opening brackets ( and n closing brackets ) so that the result is well nested: reading left to right, no prefix has more ) than (, and the totals match.
Return all such strings in any order.
Example 1
- Input:
- n = 3
- Output:
- ["((()))", "(()())", "(())()", "()(())", "()()()"]
")(" style strings such as "())(()" are excluded because a prefix closes more than it opened.
Example 2
- Input:
- n = 2
- Output:
- ["(())", "()()"]
Constraints
- 1 ≤ n ≤ 8
Hint
Show the first hint
Build the string one character at a time. When may you add '('? When may you add ')'?
Walkthrough
How to approach it
01Clarify before coding
- Only one kind of bracket? Yes, round brackets only.
- Order of the output? Any.
- How large is n? Up to 8, giving 1,430 strings (the 8th Catalan number).
02Brute force
Generate all 2^(2n) strings of '(' and ')' and keep those that pass a balance check.
Cost: O(n · 4^n): for n = 8 that is 65,536 strings checked to keep 1,430.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.