Watch 10 video solutions for Number of Great Partitions, a hard level problem involving Array, Dynamic Programming. This walkthrough by Programming Pathshala has 1,531 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109Problem Overview: You are given an integer array and a value k. Split the elements into two groups so that the sum of each group is at least k. The task is to count how many such partitions exist, returning the result modulo 1e9+7.
Approach 1: Backtracking with Pruning (Exponential time, O(2^n) time, O(n) space)
This approach explores every possible assignment of elements to two groups using recursion. At each index you place the element in group A or group B and track both running sums. Pruning reduces unnecessary work: if even after adding all remaining numbers a group cannot reach k, that branch stops early. The approach demonstrates the core idea of partitioning but still has exponential complexity in the worst case. It works for very small inputs and is useful for validating correctness before implementing the optimized solution.
Approach 2: Dynamic Programming (Subset Sum) (O(n * k) time, O(k) space)
The key observation: instead of directly counting valid partitions, count invalid ones. Any partition is invalid if one group has sum k. When the total array sum is at least 2k, both groups cannot simultaneously be below k. This allows counting subsets with sum less than k using a classic subset-sum DP from dynamic programming.
Create a 1D DP array where dp[s] stores the number of subsets with sum s. Iterate through the array, updating sums backward so each element is used once. After processing all numbers, sum all dp[s] where s < k to get the number of subsets whose sum is too small. These represent invalid partitions where one side fails the requirement. Since either group could be the invalid one, multiply this count by two.
The total number of assignments of elements to two groups is 2^n. Subtract the invalid cases to get the final result: 2^n - 2 * bad (modulo 1e9+7). This transforms a combinatorial partition problem into a bounded subset-sum counting problem, reducing the complexity dramatically.
Recommended for interviews: The dynamic programming approach is what interviewers expect. Starting with a brute-force or backtracking explanation shows you understand the search space. The optimized DP solution demonstrates the key insight: counting invalid subsets with sum constraints and subtracting them from total partitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(2^n) | O(n) | Understanding the partition search space or solving very small inputs |
| Dynamic Programming (Subset Sum) | O(n * k) | O(k) | Optimal general solution when counting subsets with bounded sum |