#!/usr/bin/perl
######################################################################
#                   Paren Lister by Ryan Whitehurst                  #
#                                                                    #
# ------------------------------------------------------------------ #
# This work is hereby released into the Public Domain.  This applies #
#   worldwide. If this is not legally possible, the right is granted #
#   for anyone to use this work for any purpose without any          #
#   conditions, unless such conditions are required by law.          #
# ------------------------------------------------------------------ #
#                                                                    #
# This program is used to list all the possible valid combinations   #
#   of a given number of pairs of parentheses.                       #
######################################################################

use strict;
use warnings;

die("Invalid or missing arguments") unless($ARGV[0]>0);

my $n = $ARGV[0];
my $start = time();
(my $min, my $max) = (0, 0);
my @results = ();

sub v_parens {
	my $num = $_[0];
	my @array = ();
	my $count = 0;

	for(my $i=0;$i<2*$n;$i++) {
		if(($num & (2**$i))==(2**$i)) {
			push(@array, 1);
			++$count;
		} else {
			push(@array, 0);
			--$count;
		}
	}
	if($count==0) {
		return @array;
	} else { return (); }
}

# find $min
for(my $i=1;$i<2*$n;$i+=2) {	$min+=2**$i; }
# find $max
for(my $i=2*$n-1;$i>=$n;$i--) { $max+=2**$i; }

for(my $i=$min;$i<=$max;$i++) {
	push(@results, v_parens($i)) unless($i%2);
}

my $numresults = scalar(@results)/(2*$n);

while(scalar(@results)>0) {
	for(my $i=0;$i<2*$n;$i++) {
		if(pop(@results) == 1) {
			print "(";
		} else {
			print ")";
		}
	} print "\n";
}

print "$numresults results\n";
print "Time elapsed: " . (time() - $start) . "\n";