The problem. Given n pairs of parentheses, generate all combinations of well-formed (balanced) parentheses.
n = 3 -> ["((()))", "(()())", "(())()", "()(())", "()()()"]
n = 1 -> ["()"]A bracket string is balanced when every ) closes an earlier ( and the counts match at the end. Build it one character at a time and allow only the choices that can still lead to a balanced string: a ( while fewer than n have been used, a ) only while there are more ( than ) so far. With those two rules the tree has no dead ends — pruning so complete that the search does no wasted work at all.
function generateParenthesis(n) { const result = []; const valid = (s) => { let balance = 0; for (const ch of s) { balance += ch === "(" ? 1 : -1; if (balance < 0) return false; // a ')' with nothing to close } return balance === 0; }; const all = (s) => { // every string of '(' and ')' of length 2n if (s.length === 2 * n) { if (valid(s)) result.push(s); return; } all(s + "("); all(s + ")"); }; all(""); return result;}Time O(2²ⁿ · n), space O(n). For n = 8 that's 65,536 strings checked to keep 1,430.
A '(' is added while some are left, a ')' only when it closes something — no branch is ever wasted.
function generateParenthesis(n) { const result = []; const path = []; const build = (open, close) => { // how many '(' and ')' are used so far if (path.length === 2 * n) { result.push(path.join("")); return; } if (open < n) { // a '(' is allowed while some are left path.push("("); build(open + 1, close); path.pop(); } if (close < open) { // a ')' only if it closes something path.push(")"); build(open, close + 1); path.pop(); } }; build(0, 0); return result;}Time O(4ⁿ / √n), space O(n) beyond the output. The number of answers is the n-th Catalan number, about 4ⁿ / (n^1.5 · √π), and since no branch dead-ends, the work is that number times the length 2n.
().( first gives the answers in dictionary order.)( and needs a filter again.