Number of Great Partitions — Hard Problem & Solution

Split nums into two ordered, possibly empty groups — every element goes to exactly one group. The partition is great if both groups have a sum of at least k.

Difficulty: Hard
Topics: Arrays, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Split nums into two ordered, possibly empty groups — every element goes to exactly one group. The partition is great if both groups have a sum of at least k.

Return the number of great partitions, modulo 10⁹ + 7. Two partitions differ if any element is in a different group.

Example 1

Input: nums = [1,2,3,4], k = 4
Output: 6
Explanation: Six of the sixteen assignments leave both sides at 4 or more.

Example 2

Input: nums = [3,3,3], k = 4
Output: 0
Explanation: The total is 9, so one side is always under 4.

Example 3

Input: nums = [6,6], k = 2
Output: 2
Explanation: Each element must go to a different group.

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 10^4
1 <= k <= 10^4

How to solve Number of Great Partitions

Complementary counting. There are 2ⁿ assignments in total. Subtract the bad ones: those with a group summing below k. When sum >= 2k the two groups cannot both fall short, so the bad partitions are counted exactly twice by a single subset-sum DP over sums below k.

Approach

If sum(nums) < 2k, return 0.
Run a 0/1-knapsack dp[j] = subsets summing to exactly j, for j from 0 to k-1.
Let small be the total of dp[0..k-1].
Return 2ⁿ - 2 · small modulo 10⁹ + 7, normalising the subtraction.

Why it works

The sum >= 2k guard is what makes the doubling exact rather than an over-count: if both a subset and its complement could sum below k, that partition would be subtracted twice, and inclusion–exclusion would need a third term. With the guard, each bad partition is bad on exactly one side, so doubling a one-sided count is correct. Iterating the knapsack downwards in j is the usual 0/1 discipline — upwards would let one element be used repeatedly.

Complexity

Time — O(n · k)
Space — O(k)

Pitfalls

Without the sum >= 2k check the doubling over-subtracts and the answer goes negative.
The modular subtraction can go below zero — add the modulus before the final reduction.
Groups may be empty, and the empty group has sum 0, which is why the j = 0 bucket starts at 1.

Reference solution

Python

from typing import List

def countPartitions(nums: List[int], k: int) -> int:
    MOD = 10**9 + 7
    if sum(nums) < 2 * k:
        return 0
    dp = [0] * k
    dp[0] = 1
    for v in nums:
        for j in range(k - 1, v - 1, -1):
            dp[j] = (dp[j] + dp[j - v]) % MOD
    small = sum(dp) % MOD
    total = pow(2, len(nums), MOD)
    return (total - 2 * small) % MOD

JavaScript

var countPartitions = function(nums, k) {
    var MOD = 1000000007;
    var n = nums.length, i, j;
    var sum = 0;
    for (i = 0; i < n; i++) sum += nums[i];
    if (sum < 2 * k) return 0;
    var dp = [];
    for (j = 0; j < k; j++) dp.push(0);
    dp[0] = 1;
    for (i = 0; i < n; i++) {
        for (j = k - 1; j >= nums[i]; j--) {
            dp[j] = (dp[j] + dp[j - nums[i]]) % MOD;
        }
    }
    var small = 0;
    for (j = 0; j < k; j++) small = (small + dp[j]) % MOD;
    var total = 1;
    for (i = 0; i < n; i++) total = (total * 2) % MOD;
    var answer = (total - 2 * small % MOD) % MOD;
    return ((answer % MOD) + MOD) % MOD;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue