Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2601. Number of Great Partitions

My accepted Python solution to LeetCode problem 2601, Number of Great Partitions, running in 65ms.

  • Difficulty: Hard
  • Python
  • Runtime 65ms
  • Memory 17.3MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 65ms, memory 17.3MB, accepted 2026-01-01.

python
class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        total = sum(nums)
        
        # If total sum < 2*k, no valid partition exists
        if total < 2 * k:
            return 0
        
        # dp[i] = number of ways to get sum i for one group
        # We count invalid partitions where group1 sum < k
        dp = [0] * k
        dp[0] = 1
        
        for num in nums:
            # Iterate backwards to avoid using same number twice
            for j in range(k - 1, num - 1, -1):
                dp[j] = (dp[j] + dp[j - num]) % MOD
        
        # Total ways = 2^n
        # Invalid ways = ways where group1 < k OR group2 < k
        # = 2 * sum(dp[0..k-1]) (but we double count when both < k, impossible if total >= 2k)
        invalid = sum(dp) * 2 % MOD
        total_ways = pow(2, n, MOD)
        
        return (total_ways - invalid + MOD) % MOD

Source