Number of Great Partitions
HardPrompt
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 109 + 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 <= 10001 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This is a straightforward approach that directly models the problem statement. It explores every possible way to partition the array nums into two groups by making a binary choice for each element. For each complete partition, it checks if it satisfies the 'great' condition (both group sums are at least k).
Algorithm
- Define a recursive function, say
solve(index, sum1, sum2), whereindexis the current element being considered, andsum1,sum2are the current sums of the two groups. - Base Case: If
indexequals the length of thenumsarray, all elements have been partitioned. Check ifsum1 >= kandsum2 >= k. If both conditions are met, we have found one great partition, so return 1. Otherwise, return 0. - Recursive Step: For the element
nums[index], explore two possibilities:- Add
nums[index]to the first group: Make a recursive callsolve(index + 1, sum1 + nums[index], sum2). - Add
nums[index]to the second group: Make a recursive callsolve(index + 1, sum1, sum2 + nums[index]).
- Add
- The result for the current state is the sum of the results from these two recursive calls, taken modulo
10^9 + 7. - The initial call to start the process is
solve(0, 0, 0).
Walkthrough
The method uses a recursive function to generate all 2^n possible partitions. The state of the recursion is defined by the current index of the element being placed and the running sums of the two groups.
class Solution { private int k; private int[] nums; private int n; private int MOD = 1_000_000_007; public int countPartitions(int[] nums, int k) { this.nums = nums; this.k = k; this.n = nums.length; // Note: This will time out on larger inputs but illustrates the concept. return solve(0, 0, 0); } private int solve(int index, long sum1, long sum2) { // Base case: all elements have been partitioned if (index == n) { if (sum1 >= k && sum2 >= k) { return 1; } return 0; } // Recursive step: explore two choices for the current element // Choice 1: Add nums[index] to group 1 int count1 = solve(index + 1, sum1 + nums[index], sum2); // Choice 2: Add nums[index] to group 2 int count2 = solve(index + 1, sum1, sum2 + nums[index]); return (count1 + count2) % MOD; }}Memoization is not feasible for this approach because the sum1 and sum2 can become very large, leading to an unmanageably large state space for the memoization table.
Complexity
Time
O(2^n) For each of the `n` elements, the function branches into two recursive calls. This creates a recursion tree with `2^n` leaf nodes, leading to an exponential runtime.
Space
O(n) This is the space required for the recursion stack, where `n` is the number of elements in `nums`.
Trade-offs
Pros
Simple to understand and implement.
Directly translates the problem definition into code.
Cons
Extremely inefficient and will lead to a 'Time Limit Exceeded' (TLE) verdict for the given constraints.
The number of states to explore grows exponentially with the input size
n.
This efficient approach reframes the problem. Instead of counting 'great' partitions directly, we count the total number of partitions and subtract the 'bad' ones. A partition is 'bad' if at least one of its two groups has a sum less than k. This transformation allows us to use dynamic programming to solve a subproblem (counting subsets with a small sum), which is much faster than exploring all partitions.
Algorithm
- Calculate the total sum
Sof all elements innums. IfS < 2k, it's impossible for both groups to have a sum of at leastk. Return 0. - The total number of ways to partition
nelements into two distinct groups is2^n. - We will count the number of 'bad' partitions and subtract them from the total. A partition is bad if
sum(group1) < korsum(group2) < k. - Since
S >= 2k, the conditionssum(group1) < kandsum(group2) < kare mutually exclusive for any partition. Thus, the number of bad partitions is(partitions with sum(group1) < k) + (partitions with sum(group2) < k). - By symmetry, these two counts are identical. We only need to find the number of ways to form a subset (for one group) whose sum is less than
k. - Use dynamic programming to find the number of subsets with a sum
sfors < k. Letdp[s]be the number of subsets ofnumsthat sum tos. - Initialize a DP array
dpof sizek, withdp[0] = 1(for the empty set) and all other elements as 0. - Iterate through each
numinnums. For eachnum, update thedparray:for s from k-1 down to num,dp[s] = (dp[s] + dp[s - num]) % MOD. - After iterating through all numbers, sum up the values in the
dparray to get the total number of subsets with a sum less thank. Let this besmallSumCount. - The total number of bad partitions is
2 * smallSumCount. - The number of great partitions is
(power(2, n) - 2 * smallSumCount) % MOD. Remember to handle potential negative results by addingMODbefore the final modulo operation.
Walkthrough
The core idea is based on the principle of inclusion-exclusion: Number of Great Partitions = Total Partitions - Bad Partitions.
First, a critical observation: if the total sum S of all elements is less than 2k, no great partition is possible. In this case, the answer is 0.
Assuming S >= 2k, we proceed as follows:
- Total Partitions: For each of the
nelements, we can place it in group 1 or group 2. This gives2^ntotal partitions. - Bad Partitions: A partition
(group1, group2)is bad ifsum(group1) < korsum(group2) < k. BecauseS >= 2k, these two conditions are mutually exclusive (if one is true, the other must be false). Therefore, we can simply add their counts. - Counting Partitions with a Small Sum Group: The number of partitions where
sum(group1) < kis equal to the number of subsets ofnumsthat can be formed with a sum less thank. By symmetry, this is the same as the number of partitions wheresum(group2) < k. - Dynamic Programming: We use a DP approach, similar to the 0/1 Knapsack problem, to count the number of subsets with a sum less than
k. Letdp[s]be the number of subsets that sum tos.
class Solution { public int countPartitions(int[] nums, int k) { long totalSum = 0; for (int num : nums) { totalSum += num; } if (totalSum < 2L * k) { return 0; } int MOD = 1_000_000_007; int n = nums.length; // dp[s] = number of subsets with sum s long[] dp = new long[k]; dp[0] = 1; // For the empty subset with sum 0 for (int num : nums) { for (int s = k - 1; s >= num; s--) { dp[s] = (dp[s] + dp[s - num]) % MOD; } } long smallSumCount = 0; for (int s = 0; s < k; s++) { smallSumCount = (smallSumCount + dp[s]) % MOD; } long totalPartitions = power(2, n, MOD); long badPartitions = (2 * smallSumCount) % MOD; long greatPartitions = (totalPartitions - badPartitions + MOD) % MOD; return (int) greatPartitions; } private long power(long base, long exp, int mod) { long res = 1; base %= mod; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % mod; base = (base * base) % mod; exp /= 2; } return res; }}Complexity
Time
O(n * k) Where `n` is the number of elements in `nums` and `k` is the target sum. The nested loops for the DP calculation are the main contributors to the runtime.
Space
O(k) The space is dominated by the DP array of size `k`.
Trade-offs
Pros
Highly efficient and passes within the given time limits.
The space complexity is optimized to be linear with
k.
Cons
The logic is indirect and relies on a combinatorial insight which might not be immediately obvious.
Requires careful handling of modular arithmetic.
Solutions
Solution
class Solution {private static final int MOD = (int)1 e9 + 7;public int countPartitions(int[] nums, int k) { long s = 0; for (int v : nums) { s += v; } if (s < k * 2) { return 0; } int n = nums.length; long[][] f = new long[n + 1][k]; f[0][0] = 1; long ans = 1; for (int i = 1; i <= n; ++i) { int v = nums[i - 1]; ans = ans * 2 % MOD; for (int j = 0; j < k; ++j) { f[i][j] = f[i - 1][j]; if (j >= v) { f[i][j] = (f[i][j] + f[i - 1][j - v]) % MOD; } } } for (int j = 0; j < k; ++j) { ans = (ans - f[n][j] * 2 % MOD + MOD) % MOD; } return (int)ans; }}class Solution {public: const int mod = 1e9 + 7; int countPartitions(vector<int> &nums, int k) { long s = accumulate(nums.begin(), nums.end(), 0l); if (s < k * 2) return 0; int n = nums.size(); long f[n + 1][k]; int ans = 1; memset(f, 0, sizeof f); f[0][0] = 1; for (int i = 1; i <= n; ++i) { int v = nums[i - 1]; ans = ans * 2 % mod; for (int j = 0; j < k; ++j) { f[i][j] = f[i - 1][j]; if (j >= v) { f[i][j] = (f[i][j] + f[i - 1][j - v]) % mod; } } } for (int j = 0; j < k; ++j) { ans = (ans - f[n][j] * 2 % mod + mod) % mod; } return ans; }};class Solution: def countPartitions(self, nums: List[int], k: int) -> int: if sum(nums) < k * 2: return 0 mod = 10 ** 9 + 7 n = len(nums) f = [[0] * k for _ in range(n + 1)] f[0][0] = 1 ans = 1 for i in range(1, n + 1): ans = ans * 2 % mod for j in range(k): f[i][j] = f[i - 1][j] if j >= nums[i - 1]: f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod return (ans - sum(f[- 1]) * 2 + mod) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.