[SPOILER] Approach for QOTW 23

I just got back after a week away, and have read up to the
first few submissions without having seen the approach I first
thought of.

Build a list which contains the list of solutions for each
number of paren pairs inductively.

If you have the list of valid solutions for all lengths
containing 0..n paren pairs, it is easy to compute the list for
n+1.  Each element will look like (Xi)Xj where Xi is a solution
with i pairs, Xj is a solution with j pairs and (i+j+1) == n+1.

    my $target = shift;

    my @ans = (
	[ '' ],
	[ '()' ]
    );

    for( my $n = 1; $n < $target; ++$n) {
	my $n1 = $n + 1;
	for( my $i = 0; $i < $n; ++$i ) {
	    my $j = $n - $i;
	    for my $Xi (@{$ans[$i]}) {
		for my $Xj (@{$ans[$j]}) {
		    push( $ans[$n1], "($Xi)$Xj" );
		}
	    }
	}
    }

    print "$_\n" for @{$ans[$target]};

Because of the hugely exponential size of the the result, in
real life, I'd actually have @ans change from containing a real
array of the entire result of the length (at smaller lengths)
to instead contain a reference to a file with the results (at
larger lengths) and then have the iteration be set up to open
and read through a file when the sub-sequence being inserted
is above the size threshhold (and similarly, the results of
a new iteration would be written to a file instead of being
pushed onto an array after the threshold has been reached).
A major performance boost, at that point, would come from
choosing the larger length of i or j as the outer loop, and the
smaller as the inner loop (read a large file once and do a few
operations on each element instead of reading it a few times
doing a single operation on each element each time through)
- but that does shuffle the output order in a complex way.

--