#!/usr/bin/env perl
use strict;
use warnings;
use 5.020;
use experimental 'signatures';

my %memoize;

sub sub_combinations($n, $max_val = $n) {
    return 1 if $n == 0;

    my $key = "$n,$max_val";
    return $memoize{$key} if $memoize{$key};

    my $combinations = 0;
    for my $i (reverse 1..$n) {
        next if $i > $max_val;
        $combinations += __SUB__->($n - $i, $i);
    }
    $memoize{$key} = $combinations;
    $combinations;
}

for my $i (2..100) {
    say "$i: " . (sub_combinations($i) - 1);
}

__END__

# 1 1 2  3  5  8 13 21 34 55
# 1 3 6 10 15 21 28 36 45 55

# 1:  0  ( )                              ( )
# 2:  1  ( 1)                             ( 1)
# 3:  2  ( 1+ 1)                          ( 1+ 1)
# 4:  4  ( 2+ 1+ 1)                       ( 1+ 2+ 1)
# 5:  6  ( 2+ 2+ 1+ 1)                    ( 1+ 2+ 2+ 1)
# 6:  10 ( 3+ 3+ 2+ 1+ 1)                 ( 1+ 2+ 3+ 3+ 1)
# 7:  14 ( 3+ 4+ 3+ 2+ 1+ 1)              ( 1+ 2+ 3+ 4+ 3+ 1)
# 8:  21 ( 4+ 5+ 5+ 3+ 2+ 1+ 1)           ( 1+ 2+ 3+ 5+ 5+ 4+ 1)
# 9:  29 ( 4+ 7+ 6+ 5+ 3+ 2+ 1+ 1)        ( 1+ 2+ 3+ 5+ 6+ 7+ 4+ 1)
# 10: 41 ( 5+ 8+ 9+ 7+ 5+ 3+ 2+ 1+ 1)     ( 1+ 2+ 3+ 5+ 7+ 9+ 8+ 5+ 1)
# 11: 54 ( 5+10+10+10+ 7+ 5+ 5+ 2+ 1+ 1)  ( 1+ 2+ 3+ 5+ 7+ 9+11+11+ 6+ 1)
#
# 1 1
#
# 2 1
# 1 1 1
#
# 3 1
# 2 2
# 2 1 1
# 1 1 1 1
#
# 4 1
# 3 2
# 3 1 1
# 2 2 1
# 2 1 1 1
# 1 1 1 1 1
#
# 5 1
# 4 2
# 4 1 1
# 3 3
# 3 2 1
# 3 1 1 1
# 2 2 2
# 2 2 1 1
# 2 1 1 1 1
# 1 1 1 1 1 1
#
# 6 1
# 5 2
# 4 3
# 5 1 1
# 4 2 1
# 3 3 1
# 3 2 2
# 4 1 1 1
# 3 2 1 1
# 2 2 2 1
# 3 1 1 1 1
# 2 2 1 1 1
# 2 1 1 1 1 1
# 1 1 1 1 1 1 1
#
# 7 1
# 6 2
# 5 3
# 4 4
# 6 1 1
# 5 2 1
# 4 3 1
# 4 2 2
# 3 3 2
# 5 1 1 1
# 4 2 1 1
# 3 3 1 1
# 3 2 2 1
# 2 2 2 2
# 4 1 1 1 1
# 3 2 1 1 1
# 2 2 2 1 1
# 3 1 1 1 1 1
# 2 2 1 1 1 1
# 2 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1
#
# 8 1
# 7 2
# 6 3
# 5 4
# 7 1 1
# 6 2 1
# 5 3 1
# 5 2 2
# 4 4 1
# 4 3 2
# 3 3 3
# 6 1 1 1
# 5 2 1 1
# 4 3 1 1
# 4 2 2 1
# 3 3 2 1
# 3 2 2 2
# 5 1 1 1 1
# 4 2 1 1 1
# 3 3 1 1 1
# 3 2 2 1 1
# 2 2 2 2 1
# 4 1 1 1 1 1
# 3 2 1 1 1 1
# 2 2 2 1 1 1
# 3 1 1 1 1 1 1
# 2 2 1 1 1 1 1
# 2 1 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1
#
# 9 1
# 8 2
# 8 1 1
# 7 3
# 7 2 1
# 7 1 1 1
# 6 4
# 6 3 1
# 6 2 2
# 6 2 1 1
# 6 1 1 1 1
# 5 5
# 5 4 1
# 5 3 2
# 5 3 1 1
# 5 2 2 1
# 5 2 1 1 1
# 5 1 1 1 1 1
# 4 4 2
# 4 4 1 1
# 4 3 3
# 4 3 2 1
# 4 3 1 1 1
# 4 2 2 2
# 4 2 2 1 1
# 4 2 1 1 1 1
# 4 1 1 1 1 1 1
# 3 3 3 1
# 3 3 2 2
# 3 3 2 1 1
# 3 3 1 1 1 1
# 3 2 2 2 1
# 3 2 2 1 1 1
# 3 2 1 1 1 1 1
# 3 1 1 1 1 1 1 1
# 2 2 2 2 2
# 2 2 2 2 1 1
# 2 2 2 1 1 1 1
# 2 2 1 1 1 1 1 1
# 2 1 1 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1 1
#
# 10 1
#  9 2
#  8 3
#  7 4
#  6 5
#  9 1 1
#  8 2 1
#  7 3 1
#  7 2 2
#  6 4 1
#  6 3 2
#  5 5 1
#  5 4 2
#  5 3 3
#  4 4 3
#  8 1 1 1
#  7 2 1 1
#  6 3 1 1
#  6 2 2 1
#  5 4 1 1
#  5 3 2 1
#  4 4 2 1
#  4 3 3 1
#  4 3 2 2
#  3 3 3 2
#  7 1 1 1 1
#  6 2 1 1 1
#  5 3 1 1 1
#  5 2 2 1 1
#  4 4 1 1 1
#  4 3 2 1 1
#  4 2 2 2 1
#  3 3 3 1 1
#  3 3 2 2 1
#  3 2 2 2 2
#  6 1 1 1 1 1
#  5 2 1 1 1 1
#  4 3 1 1 1 1
#  4 2 2 1 1 1
#  3 3 2 1 1 1
#  3 2 2 2 1 1
#  2 2 2 2 2 1
#  5 1 1 1 1 1 1
#  4 2 1 1 1 1 1
#  3 3 1 1 1 1 1
#  3 2 2 1 1 1 1
#  2 2 2 2 1 1 1
#  4 1 1 1 1 1 1 1
#  3 2 1 1 1 1 1 1
#  2 2 2 1 1 1 1 1
#  3 1 1 1 1 1 1 1
#  2 2 1 1 1 1 1 1
#  3 1 1 1 1 1 1 1 1
#  2 2 1 1 1 1 1 1 1
#  2 1 1 1 1 1 1 1 1 1
#  1 1 1 1 1 1 1 1 1 1 1