Generate Parentheses
Problem
Return every well-formed string made of n pairs of parentheses.
Example 1
Input: n = 3 Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Test cases
Case 1
Input: 3 Expected (any order): ["((()))","(()())","(())()","()(())","()()()"]
Case 2
Input: 1 Expected (any order): ["()"]
Case 3
Input: 2 Expected (any order): ["(())","()()"]
View solutionHide solution1 approach
1. Backtracking with open/close counts
Time O(4^n / √n) — the nth Catalan numberSpace O(n)
Add "(" while fewer than n are open; add ")" only while it would not exceed the opens. Every leaf is valid — no filtering needed.
function generateParenthesis(n) { const res = []; const bt = (cur, open, close) => { if (cur.length === 2 * n) { res.push(cur); return; } if (open < n) bt(cur + '(', open + 1, close); if (close < open) bt(cur + ')', open, close + 1); }; bt('', 0, 0); return res;}