Given n pairs of parentheses, generate all combinations of well-formed parentheses.
Pruning invalid branches early instead of generating-then-filtering.
Track how many '(' and ')' used. You may add '(' while open < n, and ')' only while close < open (otherwise it's malformed). Pruning the impossible branches is what makes this efficient — you never build a string you'd throw away, so the recursion tree only contains valid prefixes. The two invariants (open ≤ n, close ≤ open) are exactly the well-formedness rules stated incrementally. The count of results is the nth Catalan number, hence the O(4ⁿ/√n) bound.
Generate all valid arrangements under constraints → backtrack, and prune the moment the partial becomes invalid.
Time O(4ⁿ/√n) (Catalan) · Space O(n)