### 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 [All88]:
```
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 [All88] (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 and large integers [AKS21] efficiently.

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

### References

[All88] L. Allison, 'Some Applications of Continuations', Computer Journal, 31(1), pp.9-11, doi:10.1093/comjnl/31.1.9, February 1988.

[AKS21] L. Allison, A. S. Konakurthu & D. F. Schmidt, 'On Universal Codes for Integers: Wallace Tree, Elias Omega and Beyond', Data Compression Conference, IEEE, pp.313-322, doi:10.1109/DCC50243.2021.000399, March 2021.
Also see Universal Codes.