Number of Great Partitions
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given an array nums consisting of positive integers and an integer k.
Partition the array into two ordered groups such that each element is in exactly one group. A partition is called great if the sum of elements of each group is greater than or equal to k.
Return the number ofdistinct great partitions. Since the answer may be too large, return it modulo 10^9 + 7.
Two partitions are considered distinct if some element nums[i] is in different groups in the two partitions.
Examples
Example 1
Input: nums = [1,2,3,4], k = 4
Output: 6
Explanation: The great partitions are: ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) and ([4], [1,2,3]).
Example 2
Input: nums = [3,3,3], k = 4
Output: 0
Explanation: There are no great partitions for this array.
Example 3
Input: nums = [6,6], k = 2
Output: 2
Explanation: We can either put nums[0] in the first partition or in the second partition.
The great partitions will be ([6], [6]) and ([6], [6]).
Constraints
1 <= nums.length, k <= 10001 <= nums[i] <= 10^9
Solution
Method 1 – Subset Sum DP and Inclusion-Exclusion
Intuition
Every partition splits nums into two groups. For a partition to be great, both groups must have sum >= k. The total number of partitions is 2^n. We subtract the number of partitions where at least one group has sum < k. By symmetry, this is 2 * (number of subsets with sum < k). But if both groups have sum < k, we've double-counted, so we need to add back the number of subsets with sum < k and complement also < k (which is only possible if total < 2k).
Approach
- Compute total sum S = sum(nums).
- Use DP to count the number of subsets with sum < k.
- The answer is: total_partitions = 2^n, bad_partitions = 2 * (number of subsets with sum < k), so answer = total_partitions - bad_partitions.
- If S < 2*k, answer = 0.
- Return answer modulo 1e9+7.
Code
C++
#include <vector>
#include <numeric>
using namespace std;
class Solution {
public:
int greatPartitions(vector<int>& nums, int k) {
const int MOD = 1e9+7;
int n = nums.size();
long long S = accumulate(nums.begin(), nums.end(), 0LL);
if (S < 2LL*k) return 0;
vector<long long> dp(k, 0);
dp[0] = 1;
for (int x : nums) {
for (int s = k-1; s >= x; --s) dp[s] = (dp[s] + dp[s-x]) % MOD;
}
long long bad = 0;
for (int s = 0; s < k; ++s) bad = (bad + dp[s]) % MOD;
long long ans = (modpow(2, n, MOD) - 2*bad % MOD + MOD) % MOD;
return (int)ans;
}
long long modpow(long long a, long long b, long long m) {
long long r = 1;
while (b) {
if (b&1) r = r*a % m;
a = a*a % m; b >>= 1;
}
return r;
}
};
Go
func greatPartitions(nums []int, k int) int {
const mod = 1e9+7
n := len(nums)
S := 0
for _, x := range nums { S += x }
if S < 2*k { return 0 }
dp := make([]int, k)
dp[0] = 1
for _, x := range nums {
for s := k-1; s >= x; s-- {
dp[s] = (dp[s] + dp[s-x]) % mod
}
}
bad := 0
for s := 0; s < k; s++ { bad = (bad + dp[s]) % mod }
ans := (modpow(2, n, mod) - 2*bad%mod + mod) % mod
return ans
}
func modpow(a, b, m int) int {
r := 1
for b > 0 {
if b&1 == 1 { r = r*a % m }
a = a*a % m; b >>= 1
}
return r
}
Java
class Solution {
public int greatPartitions(int[] nums, int k) {
int MOD = (int)1e9+7, n = nums.length, S = 0;
for (int x : nums) S += x;
if (S < 2*k) return 0;
long[] dp = new long[k];
dp[0] = 1;
for (int x : nums) {
for (int s = k-1; s >= x; --s) dp[s] = (dp[s] + dp[s-x]) % MOD;
}
long bad = 0;
for (int s = 0; s < k; ++s) bad = (bad + dp[s]) % MOD;
long ans = (modpow(2, n, MOD) - 2*bad % MOD + MOD) % MOD;
return (int)ans;
}
long modpow(long a, long b, long m) {
long r = 1;
while (b > 0) {
if ((b&1) == 1) r = r*a % m;
a = a*a % m; b >>= 1;
}
return r;
}
}
Kotlin
class Solution {
fun greatPartitions(nums: IntArray, k: Int): Int {
val MOD = 1_000_000_007
val n = nums.size
val S = nums.sum()
if (S < 2*k) return 0
val dp = LongArray(k)
dp[0] = 1L
for (x in nums) {
for (s in k-1 downTo x) dp[s] = (dp[s] + dp[s-x]) % MOD
}
var bad = 0L
for (s in 0 until k) bad = (bad + dp[s]) % MOD
val ans = (modpow(2L, n.toLong(), MOD) - 2*bad % MOD + MOD) % MOD
return ans.toInt()
}
fun modpow(a: Long, b: Long, m: Int): Long {
var r = 1L; var aa = a; var bb = b
while (bb > 0) {
if ((bb and 1L) == 1L) r = r*aa % m
aa = aa*aa % m; bb = bb shr 1
}
return r
}
}
Python
class Solution:
def greatPartitions(self, nums: list[int], k: int) -> int:
MOD = 10**9+7
n, S = len(nums), sum(nums)
if S < 2*k: return 0
dp = [0]*k; dp[0] = 1
for x in nums:
for s in range(k-1, x-1, -1):
dp[s] = (dp[s] + dp[s-x]) % MOD
bad = sum(dp[:k]) % MOD
ans = (pow(2, n, MOD) - 2*bad % MOD + MOD) % MOD
return ans
Rust
impl Solution {
pub fn great_partitions(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let s: i64 = nums.iter().map(|&x| x as i64).sum();
if s < 2*k as i64 { return 0; }
let m = 1_000_000_007;
let mut dp = vec![0i64; k as usize];
dp[0] = 1;
for &x in &nums {
for s in (x as usize..k as usize).rev() {
dp[s] = (dp[s] + dp[s-x as usize]) % m;
}
}
let bad: i64 = dp.iter().sum::<i64>() % m;
let ans = (modpow(2, n as i64, m) - 2*bad % m + m) % m;
ans as i32
}
}
fn modpow(a: i64, b: i64, m: i64) -> i64 {
let mut r = 1;
let mut aa = a; let mut bb = b;
while bb > 0 {
if bb & 1 == 1 { r = r*aa % m; }
aa = aa*aa % m; bb >>= 1;
}
r
}
TypeScript
class Solution {
greatPartitions(nums: number[], k: number): number {
const MOD = 1e9+7, n = nums.length, S = nums.reduce((a,b)=>a+b,0);
if (S < 2*k) return 0;
const dp = Array(k).fill(0); dp[0] = 1;
for (const x of nums) {
for (let s = k-1; s >= x; --s) dp[s] = (dp[s] + dp[s-x]) % MOD;
}
const bad = dp.reduce((a,b)=>a+b,0) % MOD;
const ans = (modpow(2, n, MOD) - 2*bad % MOD + MOD) % MOD;
return ans;
}
}
function modpow(a: number, b: number, m: number): number {
let r = 1;
while (b > 0) {
if (b & 1) r = r*a % m;
a = a*a % m; b >>= 1;
}
return r;
}
Complexity
- ⏰ Time complexity:
O(n*k), where n is the number of elements and k is the target sum. - 🧺 Space complexity:
O(k).