Backtracking · 081Medium
Generate Parentheses
Given n pairs of parentheses, generate all combinations of well-formed parentheses.
Constraints
- 1 <= n <= 8
Examples
generateParenthesis(1) -> ["()"] generateParenthesis(3) -> ["((()))","(()())","(())()","()(())","()()()"] generateParenthesis(2) -> ["(())","()()"] // any order generateParenthesis(4) -> 14 strings // the 4th Catalan number generateParenthesis(8) -> 1430 strings // the largest allowed n
Edge cases
- Every result has exactly 2n characters.
- The count of results is the nth Catalan number.
Show the target complexity (spoiler)
- Naive
- O(2^(2n) * n) time — generate every string of brackets and filter the valid ones.
- Target
- O(4^n / sqrt(n)) time — backtrack, only ever adding '(' while open < n and ')' while close < open, so invalid branches are never built.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/10-backtracking/081-generate-parentheses.js ./practice c 081