2601. Number Of Great Partitions¶

Difficulty: Hard

2601. Number of Great Partitions

Hard

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 of distinct great partitions. Since the answer may be too large, return it modulo 10⁹ + 7.

Two partitions are considered distinct if some element nums[i] is in different groups in the two partitions.

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 <= 1000
1 <= nums[i] <= 10⁹

Solution¶

import java.util.Arrays;

class Solution {
    private int mod = (int)(1e9 + 7);
    private long dp[][];
    public int countPartitions(int[] nums, int k) {
        int n = nums.length;
        long totalWays = 1;
        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            totalWays = (totalWays * 2) % mod;
            totalSum += nums[i];
        }

        if (totalSum < 2 * k)
            return 0;
        dp = new long[n + 1][k + 1];
        for (long current[] : dp)
            Arrays.fill(current, -1);

        long count = solve(0, 0, nums, k);
        long res = (totalWays - 2 * count % mod + mod) % mod;

        return (int)(res);
    }

    private long solve(int ind, int sum, int arr[], int k) {
        if (ind >= arr.length) {
            if (sum < k)
                return 1;
            return 0;
        }

        if (dp[ind][sum] != -1)
            return dp[ind][sum];

        long op1 = solve(ind + 1, sum, arr, k);
        long op2 = 0;
        if (sum + arr[ind] <= k)
            op2 = solve(ind + 1, sum + arr[ind], arr, k);

        return dp[ind][sum] = (op1 + op2) % mod;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here