I saw this on sci.math, and thought "one liner" ;-) I even think a DP non-recursive approach should be quite quick. Keeping the output in the logical order might cost a few strokes.
#!/usr/bin/perl $count = $ARGV[0]; print join "\n", pren($count), ""; sub pren { my @list = (); (my $n) = @_; if ($n == 0) {push(@list, "")} elsif($n == 1) {push(@list, "()")} elsif($n > 1) { foreach $k (0 .. $n-1) { foreach $p1 (pren($k)) { foreach $p2 (pren($n - 1 - $k)) { push @list, sprintf "(%s)%s", $p1, $p2; } } } } return @list; } ________________________ $ ./parens.pl 5 | cat -n 1 ()()()()() 2 ()()()(()) 3 ()()(())() 4 ()()(()()) 5 ()()((())) 6 ()(())()() 7 ()(())(()) 8 ()(()())() 9 ()((()))() 10 ()(()()()) 11 ()(()(())) 12 ()((())()) 13 ()((()())) 14 ()(((()))) 15 (())()()() 16 (())()(()) 17 (())(())() 18 (())(()()) 19 (())((())) 20 (()())()() 21 (()())(()) 22 ((()))()() 23 ((()))(()) 24 (()()())() 25 (()(()))() 26 ((())())() 27 ((()()))() 28 (((())))() 29 (()()()()) 30 (()()(())) 31 (()(())()) 32 (()(()())) 33 (()((()))) 34 ((())()()) 35 ((())(())) 36 ((()())()) 37 (((()))()) 38 ((()()())) 39 ((()(()))) 40 (((())())) 41 (((()()))) 42 ((((())))) () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] ____________________________________________________________________________________ Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs