#2518

Number of Great Partitions

master · 1885 · lc hard +32 · verified · 33.4% accepted · 490 likes · top 11%

Description

Given an array nums of positive integers and integer k, count the number of distinct ways to split nums into two ordered groups (each element in exactly one group) such that both groups have a sum ≥ k. Return the count modulo 10⁹ + 7. Two partitions are distinct if any element lands in different groups.

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]).

Code

1

2

3

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int: