Number of Great Partitions

Number of Great Partitions

What is this problem about?

The Number of Great Partitions problem asks you to count ways to partition an array into exactly two non-empty groups (subsets) such that both groups have sum ≥ k. Return the count modulo 10^9+7. This hard coding problem uses a complementary counting approach with subset-sum DP.

Why is this asked in interviews?

Darwinbox and Sprinklr ask this hard DP problem because the direct counting (subsets where both halves ≥ k) is complex, while the complementary approach — total partitions minus partitions where at least one part < k — is cleaner. The array and dynamic programming interview pattern is demonstrated with the inclusion-exclusion complement technique.

Algorithmic pattern used

Complementary counting + DP. Total partitions = 2^n - 2 (excluding empty and full array assignments). Subtract "bad" partitions where at least one group has sum < k. A bad partition has the first group with sum < k OR second group with sum < k. By symmetry, count partitions where first group sum < k and multiply by 2 (one side small). Use standard subset-sum DP to count subsets with sum < k, subtract from total.

Example explanation

nums=[1,2,3,4], k=4. Total partitions = 2^4 - 2 = 14. Subsets with sum < 4: {}, {1}, {2}, {3}, {1,2} (sum=3), {1,3}? sum=4, not <4. Count: 4. Bad (first group sum < k): 4 ways. Bad (second group sum < k): 4 ways. But these overlap? By symmetry just 2count - overlap. Answer = 14 - 24 + overlap = ... Careful with inclusion-exclusion. For each subset S with sum(S) < k, its complement also gets counted. Answer = 14 - 2 * (number of subsets with sum in [1, k-1]).

Common mistakes candidates make

• Direct counting (too complex — use complementary approach).
• Not handling the base case (subsets of sum 0 or total sum).
• Including the empty set or full set in bad partition count.
• Incorrect modular arithmetic in the subtraction (add mod before subtracting).

Interview preparation tip

When counting "pairs of subsets satisfying a joint condition," the complementary approach is often simpler: count total - bad. Here, bad = at least one group sum < k. By symmetry, bad = 2 * (count of subsets with sum < k) minus overlap (subsets where BOTH groups have sum < k). Subset-sum DP computes counts up to any target sum. Practice inclusion-exclusion on subset-pair counting problems — it's a standard technique for hard counting DP problems.