From 6611306654498ab7e0a7ff9cc7df9d6341eac7c8 Mon Sep 17 00:00:00 2001
From: Jesse Luehrs <doy@tozt.net>
Date: Mon, 17 Jul 2017 05:02:59 -0400
Subject: problem 76

---
 076.pl | 237 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 237 insertions(+)
 create mode 100644 076.pl

diff --git a/076.pl b/076.pl
new file mode 100644
index 0000000..16e60d1
--- /dev/null
+++ b/076.pl
@@ -0,0 +1,237 @@
+#!/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
-- 
cgit v1.2.3