#!/usr/bin/perl -l
# $Id: parens2.pl,v 1.3 2004/09/06 02:21:30 trammell Exp $
# vim: set ai expandtab ts=4 tw=72 :

use strict;
use warnings;

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

# This algorithm uses recursion with memoization.
#
# To calculate parens[N+1] from parens[N]:
#   => loop over each string element "S" in parens[N]
#   => for each of the 2N+1 character positions 0 .. 2N ("P"),
#      insert the string "()" into string S at position P
#   => collect all the modified strings
#   => remove any duplicates
#   => sort

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

print for parens($n);

my %cache;

sub uniq(@);

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

    unless (exists $cache{ $n }) {
        my @new;
        foreach my $p ( parens($n-1) ) {
            push @new, map { my $tmp = $p; substr($tmp,$_,0,"()"); $tmp } 0 .. length($p);
        }
        @new = uniq @new;
        @new = sort @new;
        $cache{ $n } = \@new;
    }

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

sub uniq (@) {
    my %seen;
    my @out;
    for (@_) {
        next if $seen{ $_ }++;
        push @out, $_;
    }
    return @out;
}

