Aggregate Sum Over Partitions With Parts at least K

Problem

Given integers N and K, find an aggregate sum of all integer partitions of N such that each partition does not contain any integer less than K.

Examples

Example 1

Input:
N = 6, K = 2
Output:
24
Explanation:
Valid partitions: [6], [4, 2], [3, 3], [2, 2, 2]. There are 4 partitions; each sums to 6, so aggregate = 6 * 4 = 24.

Example 2

Input:
N = 10, K = 3
Output:
50
Explanation:
Valid partitions: [10], [7, 3], [6, 4], [5, 5], [3, 3, 4]. Count = 5, each sums to 10 → aggregate = 10 * 5 = 50.

Example 3

Input:
N = 5, K = 6
Output:
0
Explanation:
No partition of 5 can have all parts ≥ 6, so count = 0 and aggregate = 0.

Why does Aggregate = N * P(N,K)? Because each partition contributes exactly N to the aggregate (sum of its parts). Summing over all partitions multiplies N by the count.

Solution

Observation: Every valid partition sums to N. If the number of valid partitions is P(N, K), then the aggregate sum is simply N * P(N, K).

We only need to count partitions of N whose minimum part ≥ K. Define F(n, m) = number of partitions of n with all parts ≥ m (non-decreasing order enforced by always choosing next part ≥ previous). Then answer = N * F(N, K).

Two useful recurrences:

1. Summation form (direct branching on first part x): F(n, m) = 0 if n < m F(n, m) = 1 if m ≤ n < 2m (only partition is {n}) F(n, m) = 1 + Σ_{x = m}^{n - m} F(n - x, x) otherwise.

2. Optimized two-way recurrence (include-or-skip m): F(n, m) = 0 if n < m F(n, m) = 1 if m ≤ n < 2m F(n, m) = F(n, m + 1) + F(n - m, m) otherwise. Explanation: Partitions either use at least one m (remove one m, still need parts ≥ m) or use none (all parts ≥ m+1). This removes the summation loop and yields O(n^2) time.

We present multiple methods.

Method 1 - Naive Recursion (Summation Recurrence)

Intuition

Branch on the first chosen part x (≥ current minimum m) and recursively partition the remaining n - x with new minimum x. Count all possibilities; base cases prune search.

Approach

1. Function F(n, m) with bases as above.
2. For each x in [m, n - m] add F(n - x, x) and include the partition {n} via the initial 1 when n ≥ 2m.
3. 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

C++

long long countPartitionsNaive(long long n, long long m) {
    if (n < m) return 0;
    if (n < 2*m) return 1; // only {n}
    long long total = 1;   // the partition {n}
    for (long long x = m; x <= n - m; ++x) {
        total += countPartitionsNaive(n - x, x);
    }
    return total;
}
long long aggregatePartitionSumNaive(int N, int K) {
    return (long long)N * countPartitionsNaive(N, K);
}

Go

func countPartitionsNaive(n, m int) int64 {
    if n < m { return 0 }
    if n < 2*m { return 1 }
    total := int64(1)
    for x := m; x <= n-m; x++ {
        total += countPartitionsNaive(n-x, x)
    }
    return total
}
func aggregatePartitionSumNaive(N, K int) int64 {
    return int64(N) * countPartitionsNaive(N, K)
}

Java

class PartitionNaive {
    long count(long n, long m) {
        if (n < m) return 0;
        if (n < 2*m) return 1;
        long total = 1;
        for (long x = m; x <= n - m; x++) {
            total += count(n - x, x);
        }
        return total;
    }
    long aggregatePartitionSum(int N, int K) {
        return (long)N * count(N, K);
    }
}

Python

def count_partitions_naive(n: int, m: int) -> int:
    if n < m:
        return 0
    if n < 2*m:
        return 1
    total = 1
    for x in range(m, n - m + 1):
        total += count_partitions_naive(n - x, x)
    return total

def aggregate_partition_sum_naive(N: int, K: int) -> int:
    return N * count_partitions_naive(N, K)

Complexity

• ⏰ Time complexity: O(exp) – exponential branching due to exploring many overlapping states repeatedly.
• 🧺 Space complexity: O(N) – recursion depth can grow with a chain of minimal increments.

Method 2 - Top-Down Memoization (Optimized Recurrence)

Intuition

Use the include-or-skip recurrence F(n,m) = F(n,m+1) + F(n-m,m) with memoization to avoid recomputation. This reduces time to the number of (n,m) states: O(N^2).

Approach

1. Memo table of size (N+1) x (N+2) initialized to -1.
2. Base cases as defined.
3. Recurse using optimized recurrence.
4. Aggregate sum = N * F(N,K).

Recurrence

F(n, m) = 0 if n < m F(n, m) = 1 if m ≤ n < 2m F(n, m) = F(n, m+1) + F(n-m, m) otherwise.

Code

C++

#include <vector>
using namespace std;

class PartitionMemo {
    vector<vector<long long>> memo;
    long long solve(int n, int m) {
        if (n < m) return 0;
        if (n < 2*m) return 1;
        long long &res = memo[n][m];
        if (res != -1) return res;
        res = solve(n, m+1) + solve(n - m, m);
        return res;
    }
public:
    long long aggregatePartitionSum(int N, int K) {
        memo.assign(N+1, vector<long long>(N+2, -1));
        return (long long)N * solve(N, K);
    }
};

Go

package main

func aggregatePartitionSumMemo(N, K int) int64 {
    memo := make([][]int64, N+1)
    for i := range memo { memo[i] = make([]int64, N+2); for j := range memo[i] { memo[i][j] = -1 } }
    var dfs func(int,int) int64
    dfs = func(n, m int) int64 {
        if n < m { return 0 }
        if n < 2*m { return 1 }
        if memo[n][m] != -1 { return memo[n][m] }
        memo[n][m] = dfs(n, m+1) + dfs(n-m, m)
        return memo[n][m]
    }
    return int64(N) * dfs(N, K)
}

Java

class PartitionMemo {
    long[][] memo;
    long dfs(int n, int m) {
        if (n < m) return 0L;
        if (n < 2*m) return 1L;
        if (memo[n][m] != -1L) return memo[n][m];
        memo[n][m] = dfs(n, m+1) + dfs(n - m, m);
        return memo[n][m];
    }
    long aggregatePartitionSum(int N, int K) {
        memo = new long[N+1][N+2];
        for (int i = 0; i <= N; i++) java.util.Arrays.fill(memo[i], -1L);
        return (long)N * dfs(N, K);
    }
}

Python

from functools import lru_cache

def aggregate_partition_sum_memo(N: int, K: int) -> int:
    @lru_cache(None)
    def f(n: int, m: int) -> int:
        if n < m:
            return 0
        if n < 2*m:
            return 1
        return f(n, m+1) + f(n - m, m)
    return N * f(N, K)

Complexity

• ⏰ Time complexity: O(N^2) – states (n,m) with 1 ≤ m ≤ n; each transition constant time.
• 🧺 Space complexity: O(N^2) – memo table (or recursion cache) plus recursion stack O(N).

Method 3 - Bottom-Up DP (2D Table)

Intuition

Iteratively fill dp[n][m] using the optimized recurrence so that higher m values are available when needed for smaller m.

Approach

1. Create (N+1) x (N+2) table initialized to 0.
2. Iterate m from N down to 1, and n from 0 to N:
   • If n < m: dp[n][m] = 0.
   • Else if n < 2m: dp[n][m] = 1.
   • Else: dp[n][m] = dp[n][m+1] + dp[n-m][m].
3. Answer = N * dp[N][K].

Code

C++

#include <vector>
using namespace std;

class PartitionBottomUp {
public:
    long long aggregatePartitionSum(int N, int K) {
        vector<vector<long long>> dp(N+1, vector<long long>(N+2, 0));
        for (int m = N; m >= 1; --m) {
            for (int n = 0; n <= N; ++n) {
                if (n < m) dp[n][m] = 0;
                else if (n < 2*m) dp[n][m] = 1;
                else dp[n][m] = dp[n][m+1] + dp[n - m][m];
            }
        }
        return (long long)N * dp[N][K];
    }
};

Go

func aggregatePartitionSumBU(N, K int) int64 {
    dp := make([][]int64, N+1)
    for i := range dp { dp[i] = make([]int64, N+2) }
    for m := N; m >= 1; m-- {
        for n := 0; n <= N; n++ {
            if n < m { dp[n][m] = 0 } else if n < 2*m { dp[n][m] = 1 } else { dp[n][m] = dp[n][m+1] + dp[n-m][m] }
        }
    }
    return int64(N) * dp[N][K]
}

Java

class PartitionBottomUp {
    long aggregatePartitionSum(int N, int K) {
        long[][] dp = new long[N+1][N+2];
        for (int m = N; m >= 1; m--) {
            for (int n = 0; n <= N; n++) {
                if (n < m) dp[n][m] = 0;
                else if (n < 2*m) dp[n][m] = 1;
                else dp[n][m] = dp[n][m+1] + dp[n - m][m];
            }
        }
        return (long)N * dp[N][K];
    }
}

Python

def aggregate_partition_sum_bottom_up(N: int, K: int) -> int:
    dp = [[0]*(N+2) for _ in range(N+1)]
    for m in range(N, 0, -1):
        for n in range(N+1):
            if n < m:
                dp[n][m] = 0
            elif n < 2*m:
                dp[n][m] = 1
            else:
                dp[n][m] = dp[n][m+1] + dp[n - m][m]
    return N * dp[N][K]

Complexity

• ⏰ Time complexity: O(N^2) – double loop over m and n.
• 🧺 Space complexity: O(N^2) – DP table.

Method Comparison

Method	Time	Space	Notes
1 Naive Recursion	O(exp)	O(N)	Exponential; pedagogical only
2 Memoized	O(N^2)	O(N^2)	Optimized recurrence; practical
3 Bottom-Up	O(N^2)	O(N^2)	Iterative fill; predictable cache behavior
4 Space Reduction	O(N^2)	O(N^2)	Conceptual; minimal practical gain here

Notes

• If only the aggregate sum is required, compute count then multiply by N – do not attempt to enumerate partitions (which can be huge) for large N.
• The optimized recurrence mirrors classic integer partition DP but starts at a minimum part K instead of 1.
• For very large N, counts may exceed 64-bit range; use big integers if necessary.