my $n=15;

my %memo;
my $total_calls = 0;

my @l = p($n,$n);

foreach my $t (@l) {
    print "@$t\n";
}

print scalar(@l)," partitions.\n";
print "total calls = $total_calls\n";


sub p($$) {
    my ($n,$k) = @_;
    my $m = $memo{"$n,$k"};

    if (defined $m) {
	return @$m;
    } else {
	my @l = recursive_p($n,$k);
	$memo{"$n,$k"} = \@l;
	return @l;
    }
}

sub recursive_p($$) {
    my ($n,$k) = @_;
    $total_calls++;
    return () if ($n<0);
    return ([]) if ($n==0);
    return () if ($k==0);
    return (p($n,$k-1),f($k,p($n-$k,$k)));
}

sub f($@) {
    my $k=shift;
    return map { [@$_,$k] } @_;
}