Skip to main content
Talentd

Number of Great Partitions - Solution & Explanation

HardArrayDynamic Programming8 min readAsked at: Sprinklr, Darwinbox
Practice this problem

Problem Statement

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 <= 1000
  • 1 <= nums[i] <= 109

Approach Overview

Problem 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 1: Backtracking with Pruning

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(2^n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Dynamic Programming

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.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n*k)
Space Complexity: O(k)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking with Pruning

Time Complexity: O(2^n)
Space Complexity: O(n)

Dynamic Programming

Time Complexity: O(n*k)
Space Complexity: O(k)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with PruningO(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

Video Solution

Leetcode 2518 Number of Great Partitions | Leetcode Weekly contest 325 • Programming Pathshala • 1,580 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Great Partitions easy or hard?
Number of Great Partitions is classified as a Hard problem on LeetCode with an acceptance rate around 33%. The difficulty comes from recognizing that counting invalid subsets with dynamic programming is easier than enumerating valid partitions directly.
Number of Great Partitions Python/Java solution
Python and Java implementations typically use a 1D DP array of size k and modular arithmetic with 1e9+7. Iterate through the array, update subset sums in reverse order, compute the count of sums less than k, and subtract twice that value from 2^n.
How to solve Number of Great Partitions in O(nk)?
Use a subset-sum DP that counts how many subsets produce sums from 0 to k-1. Maintain a DP array and update it backward for each number to avoid reuse. Sum all counts for sums less than k to get invalid subsets, then compute the answer as (2^n - 2 * invalid) modulo 1e9+7.
What is the best approach for Number of Great Partitions?
The most efficient solution uses dynamic programming with a subset-sum counting technique. Instead of directly counting valid partitions, compute the number of subsets whose sum is less than k. Subtract twice this value from the total number of assignments (2^n) to get the valid partitions. This approach runs in O(n * k) time and O(k) space.
Is Number of Great Partitions asked at Google/Amazon/Meta?
Partitioning and subset-sum counting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test dynamic programming fundamentals, combinatorics, and the ability to transform a counting problem into a DP formulation.
What data structure is used in Number of Great Partitions?
The optimized solution uses a dynamic programming array to track the number of ways to form subset sums. The input is processed as an array, and the DP table stores counts for sums below k while iterating through the numbers.
What is the time complexity of Number of Great Partitions?
The optimal dynamic programming solution runs in O(n * k) time where n is the number of elements and k is the minimum required sum for each partition. Space complexity is O(k) using a 1D DP array that tracks subset counts for sums below k.

Ready to solve this problem?

Practice Number of Great Partitions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Partitions With Max-Min Difference at Most K

Next

Find the Punishment Number of an Integer