Generate all balanced bracket sequences

Question

Produce all well-formed strings of n pairs of parentheses. "Well-formed" means every ( is eventually closed and no ) ever appears without a matching open before it. Return every balanced sequence of n pairs. The number of them is the nth Catalan number.

Accepted Answer

Build the string character by character, tracking how many opens and closes you have placed. You may add ( while opens remain below n, and you may add ) only while closes trail opens (otherwise the string would go unbalanced). When the string reaches length 2n it is guaranteed valid, so record it. Tracing n = 2: the search yields "(())" (open, open, close, close) and "()()", the only two balanced strings. Time and space are output-sensitive (Catalan-many results, each length 2n); recursion depth is O(n). Edge cases: n = 0 returns [""], the single empty balanced string. Takeaway. Enforcing the…

Generate all balanced bracket sequences

Your answer

More Coding questions