#!/usr/bin/perl -l
# $Id: trammell.pl,v 1.2 2004/09/07 13:59:23 trammell Exp $
# vim: set ai expandtab ts=4 :

use strict;
use warnings;

sub usage { die "@_\nusage: $0 depth\n" }

@ARGV or usage();
(my $n = $ARGV[0]) =~ /\d+/ or usage;

print for parens($n);

my %cache;

sub parens {
    my $n = $_[0]; 
    return ('') if $n == 0;
    return ("()") if $n == 1;

    unless (exists $cache{ $n }) {
        my @p = map {("$_()","($_)","()$_")} parens($n-1);
        foreach my $i ( 1 .. $n-1 ) {
            push @p, map { my $x = $_; map { "$x$_" } parens($i) } parens($n-$i);
        }
        $cache{ $n } = [ uniq(@p) ];
    }

    return @{ $cache{ $n } };
}

sub uniq { sort keys %{{ map { $_, 1 } @_ }}; }

