For the first one, here's a breadth first expansion solution...

#!/usr/bin/perl -l

# http://perlmonks.org/?node_id=1194483

use strict;
use warnings;

my $n = shift // 3;

my %seen;
my @fifo = '';

while( $fifo[0] =~ tr/(// < $n )
  {
  $_ = shift @fifo;
  !$seen{"$`()$'"}++ && push @fifo, "$`()$'" while /()/g;
  }

print for reverse sort @fifo;
[download]