use Memoize; memoize 'int_partitions'; ## number of integer partitions of $N with smallest part $min sub int_partitions { my ($N, $min) = @_; $min = 1 if not defined $min; ## only one way to split up 0 return 1 if $N == 0; ## the smallest item in the partition can be between $min .. $N ## and after we fix it, we need to partition the remaining ## $N-$_, into pieces that must all be >= $_ my $total = 0; for ($min .. $N) { $total += int_partitions($N-$_, $_); } return $total; } print int_partitions(shift), $/;