--- a/dynprog.cc	Sun Mar 19 21:58:20 2023 +0100
+++ b/dynprog.cc	Wed Mar 22 21:54:12 2023 +0100
@@ -5,6 +5,7 @@
 #include <iostream>
 #include <numeric>
 #include <ranges>
+#include <set>
 #include <sstream>
 #include <string>
 #include <tuple>
@@ -313,6 +314,37 @@
     return max_len;
 }
 
+// https://www.techiedelight.com/coin-change-problem-find-total-number-ways-get-denomination-coins/
+int coin_change_problem(const vector<int>& coins, int amount_left, vector<int>& current, set<vector<int>>& possibilities) {
+    if (amount_left == 0 && !current.empty()) {
+        vector<int> current_{current};
+        sort(current_.begin(), current_.end());
+        possibilities.insert(current_);
+        return 1;
+    } else if (amount_left > 0) {
+        int possible_count = 0;
+        for (int coin : coins) {
+            if (coin > amount_left) continue;
+            current.push_back(coin);
+            possible_count += coin_change_problem(coins, amount_left-coin, current, possibilities);
+            current.pop_back();
+        }
+        return possible_count;
+    }
+    return 0;
+}
+
+void evaluate_coin_change() {
+    vector<int> coins{1, 3, 5, 7};
+    int amount = 8;
+    vector<int> current{};
+    set<vector<int>> possibilities{};
+
+    int N = timeit_f([&]() -> int { return coin_change_problem(coins, amount, current, possibilities); });
+
+    fmt::print("{}: {}\n", possibilities.size(), possibilities);
+}
+
 int lcss_main(void) {
 
     vector<int> a{1, 6, 2, -1, 3, 55, 2, 4, 23, 5, 6, 7, 8, 9, 10};
@@ -332,6 +364,6 @@
 }
 
 int main(void) {
-    fmt::print("{}\n", rodcutting_prod_max(4));
+    evaluate_coin_change();
     return 0;
 }