2518. Number of Great Partitions


Problem Description

In this problem, we are given an array called nums which contains positive integers and another integer k. Our task is to find out how many distinct ways (great partitions) there are to split the array into two groups such that the sum of the numbers in each group is at least k. A great partition means that neither of the two groups has a sum that is less than k.

Each element from the array nums must be put into one, and only one, of the two groups. The order of elements within the groups is not important, but distinct partitions are those where at least one element appears in a different group compared to another partition.

Since there can be many distinct great partitions, we are required to return this number modulo 10^9 + 7 to keep the number manageable and within the bounds of typical integer limits.

One key point to understand is that if the sum of all elements in the array is less than 2k, we cannot possibly form two groups each having a sum greater or equal to k, hence the answer is straightforwardly 0 in such cases.

Intuition

To find the number of distinct great partitions, we can start by considering a dynamic programming approach that helps us understand whether it is possible to reach a certain sum with a subset of the given elements. The primary intuition behind the solution is to build up the count of subsets that can make up sums from 0 to k-1 respectively since sums from k to 2k-1 will automatically form a partition where both groups have at least k.

To arrive at the solution, we initialize a matrix 'f' with dimensions (n+1) x k where n is the number of elements in nums. Each f[i][j] will represent the number of ways we can achieve a sum j using the first i numbers of the array nums.

At the start, we have only one way to achieve a sum of 0, which is by choosing no elements (f[0][0] = 1). As we iterate over the elements of nums, we keep updating the matrix based on whether we include the current element in the subset or not. This helps us accumulate counts of all possible subset sums up to k.

The total number of subsets of nums is 2^n. When building our dynamic programming matrix, we are actually counting the number of subsets that reach every possible sum less than k. These counts have to be subtracted from the total since combining them with their complements does not yield a great partition—because at least one of the groups would have a sum of less than k.

Once we calculate the subset counts, the final answer is adjusted to account for duplications and to ensure the result falls within the desired modulus of 10^9 + 7. Specifically, we:

  • Multiply the number of all subsets (2^n) by 2 modulo 10^9 + 7.
  • Subtract twice the sum of subsets that have a sum less than k from the total count.
  • Add the modulus to ensure non-negativity, then take the result modulo 10^9 + 7 to get the final answer.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a dynamic programming approach to solve the partition problem. Here's how the steps of the algorithm unfold:

  1. First, we check if the total sum of the array is less than 2k. If it is, we immediately know it's impossible to partition the array into two groups each with a sum greater than or equal to k, so we return 0.

  2. We define a two-dimensional array f with n+1 rows and k columns. n is the length of the input array nums. We initialize the first row, which corresponds to using 0 elements from the array, such that f[0][0] is 1 (one way to make a sum of 0 with 0 elements) and the rest are 0.

  3. We then use nested loops to fill in the dynamic programming matrix f. The outer loop runs through elements of nums from 1 to n, inclusive. The inner loop runs through all possible sums j from 0 to k-1, inclusive.

  4. For each element i and each sum j, f[i][j] is updated to be the sum of:

    • f[i - 1][j], which is the count of ways to reach the sum j without using the i-th element.
    • If j is greater than or equal to nums[i - 1] (the current element we're considering), we add f[i - 1][j - nums[i - 1]] to the count, which represents using the i-th element to reach the sum j.
  5. All computations are done modulo 10^9 + 7 to ensure we don't encounter integer overflow and that all operations fit within the specified modulus. This is why we see % mod after every arithmetic operation.

  6. As we calculate f[i][j], we also keep a running total of all possible subsets (represented by ans) by repeatedly doubling (ans * 2 % mod) since every element either can be included or excluded from a set.

  7. After filling out the dynamic programming matrix, we calculate the final answer. We know ans is the count of all subsets, but we want to exclude the cases where subsets sum to less than k. We sum up all f[n][j] for j from 0 to k-1 (which are the counts of subsets that don't form a great partition) and subtract twice this sum from ans. We multiply by 2 because for each such subset that forms a sum less than k, both it and its complement would be counted in ans, but neither makes a great partition.

  8. Finally, in case the subtraction makes the number negative, we add mod (which has no effect modulo mod) before taking the modulo to get the non-negative remainder within the desired range.

From a data structure perspective, we utilize a 2D array (list of lists in Python) to store the number of ways to achieve each possible sum with different subsets of the array. The dynamic programming matrix (f) is central to this solution, allowing us to build up the solution incrementally.

The code is a direct implementation of this dynamic programming approach, using the patterns of modularity arithmetic to ensure all operations stay within bounds of the problem's specifications.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's walk through an example to illustrate the solution approach using a small array. Suppose we have an array nums = [1, 2, 3] and an integer k = 3.

  1. The total sum of the array 1 + 2 + 3 is 6, which is greater than 2*k (6), so it's possible to have two groups each with a sum of at least k.

  2. We define a dynamic programming matrix f with dimensions 4 x 3 (n+1 x k), as there are 3 elements in nums and we need to consider sums up to k-1 which is 2.

  3. Initialize f to have the first row as [1, 0, 0] representing there is one way to reach a sum of 0 with 0 elements.

  4. We fill in the matrix f. Iterating over nums and possible sums, the updated matrix would look like this at each step:

    • Include the first element (1):

      1f = [
      2  [1, 0, 0],
      3  [1, 1, 0], // Include or exclude the 1
      4  [1, 0, 0],
      5  [1, 0, 0]
      6]
    • Include the second element (2):

      1f = [
      2  [1, 0, 0],
      3  [1, 1, 0],
      4  [1, 1, 1], // Include or exclude the 2 (we can now reach sums 1 and 2 using 1 and/or 2)
      5  [1, 0, 0]
      6]
    • Include the third element (3):

      1f = [
      2  [1, 0, 0],
      3  [1, 1, 0],
      4  [1, 1, 1],
      5  [1, 2, 2]  // Include or exclude the 3 (we can reach sums 1 and 2 using combinations of 1, 2, and 3)
      6]
  5. All operations are done modulo 10^9 + 7.

  6. The total number of subsets is 2^n = 2^3 = 8. We double this to account for all possible subsets and exclude invalid subsets later. Thus ans = 16 % (10^9 + 7).

  7. From the matrix f, the subset counts for sums less than k are f[3][0], f[3][1], and f[3][2], which are 1, 2, and 2, respectively. Summing these up gives us 1 + 2 + 2 = 5.

  8. Subtracting twice this sum from ans we get: 16 - 2*5 = 6. We add 10^9 + 7 to ensure non-negativity and take modulo 10^9 + 7 to appear within bounds, which in this case just confirms 6 as the final count of great partitions.

So, for the given nums = [1, 2, 3] and k = 3, the number of distinct great partitions is 6. These partitions are:

  • {1, 2} & {3}
  • {1, 3} & {2}
  • {2, 3} & {1}
  • {1} & {2, 3}
  • {2} & {1, 3}
  • {3} & {1, 2}

Solution Implementation

1class Solution:
2    def countPartitions(self, nums: List[int], k: int) -> int:
3        # Check if the total sum of nums is less than the double of k
4        # In that case, there would be no way to partition the nums into k equal-sum parts
5        if sum(nums) < k * 2:
6            return 0
7
8        # Define a modulus number for the result to prevent integer overflow
9        mod = 10**9 + 7
10
11        # Get the length of the nums list
12        n = len(nums)
13
14        # Initialize a 2D array to use for dynamic programming
15        # Dimensions are (n+1) x k, and it will hold the number of ways to reach a certain sum
16        dp = [[0] * k for _ in range(n + 1)]
17
18        # Base case: There's one way to have a sum of 0 (with no elements)
19        dp[0][0] = 1
20
21        # Variable to store the answer
22        ans = 1
23
24        # Iterate over the range from 1 to n inclusive
25        for i in range(1, n + 1):
26            # Double the answer on each iteration
27            ans = ans * 2 % mod
28
29            for j in range(k):
30                # Carry over the previous count for this sum
31                dp[i][j] = dp[i - 1][j]
32
33                # If the current number can be used to build up the sum
34                if j >= nums[i - 1]:
35                    # Add the number of ways to reach the sum without the current number
36                    dp[i][j] = (dp[i][j] + dp[i - 1][j - nums[i - 1]]) % mod
37      
38        # Use the final answers in dp to adjust the overall answer
39        # Subtract twice the sum of all counts for partitions of size (k-1)
40        # Adding mod before taking mod again for handling negative values
41        return (ans - sum(dp[-1]) * 2 + mod) % mod
42
1class Solution {
2    // Defining the MOD constant as per the problem constraints
3    private static final int MOD = (int) 1e9 + 7;
4
5    // Method to count the number of ways to partition the array into two non-empty parts
6    // such that the difference between their sums is equal to k
7    public int countPartitions(int[] nums, int k) {
8        // Calculate the total sum of the array
9        long totalSum = 0;
10        for (int num : nums) {
11            totalSum += num;
12        }
13      
14        // If the sum is less than 2k, we can't partition the array as requested
15        if (totalSum < k * 2) {
16            return 0;
17        }
18      
19        // Length of the input array
20        int n = nums.length;
21      
22        // Dynamic programming array to hold counts for subproblems
23        // f[i][j] will store the count of partitions for the first 'i' numbers that have sum 'j' in one part
24        long[][] dpCounts = new long[n + 1][k];
25      
26        // Base case: for zero numbers, there's one way to achieve a sum of 0 (empty set)
27        dpCounts[0][0] = 1;
28      
29        // This will hold the final answer
30        long answer = 1;
31      
32        for (int i = 1; i <= n; ++i) {
33            int currentValue = nums[i - 1];
34            // Update the answer as we consider the current element
35            answer = answer * 2 % MOD;
36            for (int j = 0; j < k; ++j) {
37                // Count the subsets excluding the current value (carry over from the previous step)
38                dpCounts[i][j] = dpCounts[i - 1][j];
39                // Count the subsets including the current value, if it can be part of the subset
40                if (j >= currentValue) {
41                    dpCounts[i][j] = (dpCounts[i][j] + dpCounts[i - 1][j - currentValue]) % MOD;
42                }
43            }
44        }
45      
46        // Subtracting the invalid partitions from the total answer (double counted subsets)
47        // Loop only up to k to consider only one side of the partition
48        for (int j = 0; j < k; ++j) {
49            answer = (answer - dpCounts[n][j] * 2 % MOD + MOD) % MOD;
50        }
51      
52        // Return the final answer converted to an integer
53        return (int) answer;
54    }
55}
56
1#include <vector>
2#include <numeric>
3#include <cstring> // Include header for memset
4
5class Solution {
6public:
7    // Declare the MOD as a constant with a more descriptive name and use upper case for constants
8    const int MODULO = 1e9 + 7;
9
10    // Count the number of valid partitions that can divide the given set into k subsets
11    int countPartitions(std::vector<int>& nums, int k) {
12        // Calculate the sum of all elements in the array
13        long long totalSum = std::accumulate(nums.begin(), nums.end(), 0LL);
14        // If the total sum is less than 2k, no valid partitions exist
15        if (totalSum < k * 2) return 0;
16
17        // Get the number of elements in nums
18        int numCount = nums.size();
19        // Create a 2D DP array to store the intermediate results
20        long long dp[numCount + 1][k];
21        // Initialize the answer to 1
22        int result = 1;
23
24        // Clear the DP array with zeroes using memset
25        memset(dp, 0, sizeof dp);
26        // The base case: there's one way to partition zero elements into subsets of sum zero
27        dp[0][0] = 1;
28
29        // Populate the DP array
30        for (int i = 1; i <= numCount; ++i) {
31            int value = nums[i - 1];
32            // Update the result by multiplying it by 2 modulo MODULO
33            result = static_cast<int>((result * 2LL) % MODULO);
34            for (int j = 0; j < k; ++j) {
35                // Carry over the count from the previous row (excluding the current number)
36                dp[i][j] = dp[i - 1][j];
37                // If the current sum can accommodate the value, include it
38                if (j >= value) {
39                    dp[i][j] = (dp[i][j] + dp[i - 1][j - value]) % MODULO;
40                }
41            }
42        }
43
44        // Subtract the counts of partitions of all sums except k (sum we're interested in)
45        for (int j = 0; j < k; ++j) {
46            // Must ensure we're working with positive modulo for the subtracted value
47            result = (result - dp[numCount][j] * 2 % MODULO + MODULO) % MODULO;
48        }
49
50        // Return the final result
51        return result;
52    }
53};
54
1// Import array utility functions from lodash
2import _ from "lodash";
3
4// Constant to represent the modulo operation for large numbers
5const MODULO: number = 1e9 + 7;
6
7// Function to count the number of valid partitions that can divide the given set into k subsets
8function countPartitions(nums: number[], k: number): number {
9    // Calculate the sum of all elements in the array
10    let totalSum: number = _.sum(nums);
11    // If the total sum is not enough to form k partitions, return 0
12    if (totalSum < k * 2) return 0;
13
14    // Get the number of elements in nums
15    let numCount: number = nums.length;
16    // Initialize a 2D DP array with zeros
17    let dp: number[][] = _.times(numCount + 1, () => _.times(k, _.constant(0)));
18    // The base case: there's one way to partition zero elements into subsets of sum zero
19    dp[0][0] = 1;
20
21    // Populate the DP array with the number of partitions
22    for (let i = 1; i <= numCount; i++) {
23        let value: number = nums[i - 1];
24        for (let j = 0; j < k; j++) {
25            // Carry over the count from the previous row (excluding the current number)
26            dp[i][j] = dp[i - 1][j];
27            // If the current sum can fit the value, include it in the partition
28            if (j >= value) {
29                dp[i][j] = (dp[i][j] + dp[i - 1][j - value]) % MODULO;
30            }
31        }
32    }
33
34    // All possible subsets divided by including or excluding the current element
35    let result: number = _.reduce(_.range(k), (acc, j) => {
36        return (acc - dp[numCount][j] * 2 % MODULO + MODULO) % MODULO;
37    }, 1);
38
39    // Adjust the result by taking into account the number of subsets that have the sum of k
40    result = (result + dp[numCount][k]) % MODULO;
41
42    // Return the final count of the number of valid partitions
43    return result;
44}
45

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed based on the nested loops it uses:

  • There is an outer loop iterating over the array nums with n elements.
  • Inside this outer loop, there is an inner loop that iterates k times.

Each operation inside the inner loop executes in constant time. Therefore, the total number of operations performed will be O(n * k).

Hence, the time complexity of the code is O(n * k).

Space Complexity

To analyze space complexity, we look at the memory allocation:

  • The 2D list f of size (n+1) * k is the primary memory consumer, where n is the length of nums and k is the provided partition value.

No other significant memory usage is present that scales with the input size. Therefore, the space complexity is determined by the size of this 2D list.

Hence, the space complexity of the code is O(n * k).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄