### Matched brackets (parentheses)

 LA home Computing Algorithms  glossary  Recursion   Linear   Binary   Permutations   Partition   N-Queens   N-Queens 3D   Necklaces   Subgraphs   Brackets   Self-Ref   brackets also see   in Pascal
Problem: Enumerate (generate) all sequences of 'n' pairs of matched brackets (parentheses), where n ≥ 0.

Note that if [n] is a solution for n pairs,
then it must be of the form   "(" [i] ")" [n-i-1],
where 0≤i<n, [i] is a solution for 'i' pairs, and [n-i-1] is a solution for 'n-i-1' pairs.

The problem is equivalent to generating all rooted, ordered, k-ary trees of n+1 nodes,
```e.g., n=0,  .  ~   ( )

e.g., n=5,  .
/ \
.   .
|  ~ ( ()((()())) )
.
/ \
.   .
```
n=
count=
A solution using continuations:
```
function brackets(n)
{ var count = 0, seq = "";

var start  = function(p)
{ seq = ""; p(); };

var finish = function( )
{ print(cols(++count,3) + ": " + seq + ".\n"); };

var b = function( before, n, after )
{ var i;

var bPlus = function(q)
{
var beforeOpen = function(p)
{ var openP = function( ) { seq+="("; p(); };

before(openP);
};//beforeOpen()

var closeQ = function() { seq+=")"; q(); };

b( beforeOpen, i, closeQ );
};//bPlus(q)

if( n == 0 ) before( after );  // done
else
for( i = 0; i < n; i ++ )
b( bPlus, n-i-1, after );
};//b(before,n,after)

b(start, n, finish);

return count;
}//brackets(n)
```
 brackets(n) is a wrapper. b(before,n,after) does most of the work. before, and after are continuations (functions) to be called in front of, and following, each solution for n. bplus is the continuation to call in front of each part-solution generated by b(bPlus, n-i-1, after)

If '(' < ')', the solutions are generated in reverse lexicographical order.
Exercise: Make them come out in lexicographical (alphabetic) order.

BTW, another angle on the problem is to generate all sequences of n '('s and n ')'s, such that every prefix, S1..i, of a sequence, S1..2n, contains at least as many '('s as ')'s. This recalls ways of encoding trees efficiently.

Thanks to njh for reminding me of an old problem -- LA, 8/2012.