x in [m, n - m] add F(n - x, x) and include the partition {n} via the initial 1 when n ≥ 2m.

Answer = N * F(N, K).

Pseudocode

function F(n, m):
  if n < m: return 0
  if n < 2*m: return 1   # only {n}
  total = 1               # partition {n}
  for x in [m .. n - m]:
      total += F(n - x, x)
  return total

Code

[{"language":"C++","code":"long long countPartitionsNaive(long long n, long long m) {\n    if (n < m) return 0;\n    if (n < 2*m) return 1; // only {n}\n    long long total = 1;   // the partition {n}\n    for (long long x = m; x <= n - m; ++x) {\n        total += countPartitionsNaive(n - x, x);\n    }\n    return total;\n}\nlong long aggregatePartitionSumNaive(int N, int K) {\n    return (long long)N * countPartitionsNaive(N, K);\n}","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">long</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> long</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> countPartitionsNaive</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">long</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> long</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">long</span><s

Related Tags