Number of Great Partitions

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

1
2
3


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

1
2
3


Input: nums = [3,3,3], k = 4
Output: 0
Explanation: There are no great partitions for this array.

Example 3

1
2
3
4


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 <= 1000
1 <= 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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).

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Subset Sum DP and Inclusion-Exclusion#

Intuition#

Approach#

Code#

Complexity#