For everyone coming here in search of an implementation:
I used the code snippet from the original question and wrote a command line tool for it. When compiled it takes n and m as command line arguments (with input parsing yoinked from https://stackoverflow.com/a/2797823/25165526)
I also included caching to drastically speed up run time. (for inputs n = 134, m = 32 it went from 44 seconds to 0.008 seconds)
#include <iostream>
#include <string>
#include <utility>
#include <unordered_map>
#include <boost/container_hash/hash.hpp>
long long p (long long n, long long m) {
using pair = std::pair<int, int>;
static std::unordered_map<pair, long long, boost::hash<pair>> cache = {};
pair key = pair(n, m);
if (cache.contains(key)) {
return cache[key];
}
long long intermediate;
if (n == m) {
intermediate = 1 + p(n, m - 1);
cache[key] = intermediate;
return intermediate;
}
if (m == 0 || n < 0) {
cache[key] = 0;
return 0;
}
if (n == 0 || m == 1) {
cache[key] = 1;
return 1;
}
intermediate = p(n, m - 1) + p(n - m, m);
cache[key] = intermediate;
return intermediate;
}
int parse_arg(std::string arg) {
try {
std::size_t pos;
int x = std::stoi(arg, &pos);
if (pos < arg.size()) {
std::cerr << "Trailing characters after number: " << arg << '\n';
}
return x;
} catch (std::invalid_argument const &ex) {
std::cerr << "Invalid number: " << arg << '\n';
} catch (std::out_of_range const &ex) {
std::cerr << "Number out of range: " << arg << '\n';
}
return -1;
}
int main(int argc, char *argv[]) {
if (argc != 3) {
std::cout << "Use with arguments <n> <k> where n is the target value and k is the maximum value a sum element may have" << std::endl;
return -1;
}
// parse inputs
int n, k;
n = parse_arg((std::string) argv[1]);
k = parse_arg((std::string) argv[2]);
// calculate all possible sums
long long possible_sums = p(n, k);
std::cout << possible_sums << std::endl;
return 0;
}
comopiled with:
g++ -std=c++20 -o integer_partition integer_partition.cpp