The first is a non-solution in my books, but the second is very good. But I was wondering if it was possible to do a reasonable non-recursive solution, and at 87 by my count, 94 counting the body, it seems like the best so far.

sub P{
$n=pop;@a=[0];map{$i=$_;push@{$a[$i+$_]},map[$i,@$_],@{$a[$_]}for
0..$n}1..$n;@{$a[$n]}
}
[download]

I keep on thinking this should be improvable, but darned if I can see it.