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.
This approach relies on generating all possible partitions using backtracking and then checks if each partition meets the criteria.
During generation, we calculate the sum when adding an element to a group and decide if we need to prune the branch based on the sum.
This code generates all possible combinations using Python's itertools library to simulate partitions. It then checks for valid partitions based on the given condition.
Pruning is done based on initial checks before deeply branching.
Time Complexity: O(2^n)
Space Complexity: O(n)
This dynamic programming approach aims to construct possible partitions by calculating the possible sums for each subset in the array, leveraging previously calculated solutions.
The idea is to reduce subproblems by keeping track of the number of ways to achieve certain sums.
This C++ implementation uses dynamic programming to efficiently calculate the number of possible partitions that meet the condition. The table tracks the number of ways to achieve specific sums using a bottom-up approach.
C++
JavaScript
Time Complexity: O(n*k)
Space Complexity: O(k)
| Approach | Complexity |
|---|---|
| Backtracking with Pruning | Time Complexity: O(2^n) |
| Dynamic Programming | Time Complexity: O(n*k) |
| Default Approach | — |
| 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 |
Leetcode 2518 Number of Great Partitions | Leetcode Weekly contest 325 • Programming Pathshala • 1,531 views views
Watch 9 more video solutions →Practice Number of Great Partitions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor